14

我正在为基本的 Java 考试练习过去的试卷,我发现很难让 for 循环工作来测试一个数字是否是素数。我不想通过为更大的数字添加效率措施来使其复杂化,只是至少适用于 2 位数的数字。

目前,即使 n 是素数,它也总是返回 false。

我认为我的问题是我对 for 循环本身以及将“返回真”放在哪里有问题;和“return false;”......我敢肯定这是我犯的一个非常基本的错误......

public boolean isPrime(int n) {
    int i;
    for (i = 2; i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

我在 stackoverflow 其他地方找不到帮助的原因是因为类似的问题要求更复杂的实现以更有效的方式实现。

4

12 回答 12

31

你的for循环有一个小问题。它应该是: -

for (i = 2; i < n; i++)  // replace `i <= n` with `i < n`

当然,您不想在n除以时检查余数n。它会一直给你1

实际上,您甚至可以通过将条件更改为 - 来减少迭代次数i <= n / 2。因为n不能除以大于 的数n / 2,除非我们考虑n,我们根本不必考虑。

因此,您可以将for循环更改为: -

for (i = 2; i <= n / 2; i++)  
于 2013-02-01T16:10:51.213 回答
31

您可以更早地停止并更快地跳过循环:

public boolean isPrime(long n) {
    // fast even test.
    if(n > 2 && (n & 1) == 0)
       return false;
    // only odd factors need to be tested up to n^0.5
    for(int i = 3; i * i <= n; i += 2)
        if (n % i == 0) 
            return false;
    return true;
}
于 2013-02-01T16:18:56.783 回答
3

你应该写i < n,因为最后一个迭代步骤会给你true

于 2013-02-01T16:11:55.207 回答
3

错误是 i<=n

for (i = 2; i<n; i++){
于 2013-02-01T16:12:24.380 回答
2
public class PrimeNumberCheck {
  private static int maxNumberToCheck = 100;

  public PrimeNumberCheck() {
  }

    public static void main(String[] args) {
      PrimeNumberCheck primeNumberCheck = new PrimeNumberCheck();

      for(int ii=0;ii < maxNumberToCheck; ii++) {
        boolean isPrimeNumber = primeNumberCheck.isPrime(ii);

      System.out.println(ii + " is " + (isPrimeNumber == true ? "prime." : "not prime."));
    }
  }

  private boolean isPrime(int numberToCheck) {    
    boolean isPrime = true;

    if(numberToCheck < 2) {
      isPrime = false;
    }

    for(int ii=2;ii<numberToCheck;ii++) {
      if(numberToCheck%ii == 0) {
        isPrime = false;
        break;
      }
    }

    return isPrime;
  }
}
于 2013-02-01T17:31:13.670 回答
1

使用此代码号可被 3 整除,将跳过 for 循环代码初始化。
For 循环迭代也将跳过 3 的倍数。

private static boolean isPrime(int n) {

    if ((n > 2 && (n & 1) == 0) // check is it even
       || n <= 1  //check for -ve
       || (n > 3 && (n % 3 ==  0))) {  //check for 3 divisiable
            return false;
    }

    int maxLookup = (int) Math.sqrt(n);
    for (int i = 3; (i+2) <= maxLookup; i = i + 6) {
        if (n % (i+2) == 0 || n % (i+4) == 0) {
            return false;
        }
    }
    return true;
}
于 2015-09-03T20:25:07.747 回答
1

您还可以在 for 循环中为此使用一些简单的 Math 属性。

当且仅当它可以被自己整除或被 1 整除时,数字“n”才会是素数。如果数字不是素数,它将有两个因数:

n = a * b

您可以使用for循环检查直到数字'n'的sqrt,而不是一直到'n'。如果 'a' 和 'b' 都大于数字 'n' 的 sqrt,则 a*b 将大于 'n'。所以至少有一个因子必须小于或等于平方根。

所以你的循环将如下所示:

for(int i=2; i<=Math.sqrt(n); i++)

通过这样做,您将大大降低代码的运行时间复杂度。我认为它会归结为 O(n/2)。

于 2017-04-09T04:35:29.777 回答
1

最快的方法之一是只循环到 n 的平方根。

  private static boolean isPrime(int n){
        int square = (int)Math.ceil((Math.sqrt(n)));//find the square root
        HashSet<Integer> nos = new HashSet<>(); 
        for(int i=1;i<=square;i++){
            if(n%i==0){
                if(n/i==i){
                    nos.add(i);
                }else{
                    nos.add(i);
                    int rem = n/i;
                    nos.add(rem);
                }
            }
        }
        return nos.size()==2;//if contains 1 and n then prime
    }
于 2017-04-26T05:36:54.307 回答
0

您正在检查。因此i<=n,何时i==n,您只会得到 0,并且它总是会返回 false 。尝试。i<=(n/2)无需检查,直到i<n

于 2013-02-01T16:11:29.780 回答
0

上述算法将 1 视为素数,尽管它不是。因此,这是解决方案。

static boolean isPrime(int n) {
  int perfect_modulo = 0;
  boolean prime = false;

  for ( int i = 1; i <=  n; i++ ) {
    if ( n % i == 0 ) {
      perfect_modulo += 1;
    }
  }
  if ( perfect_modulo == 2 ) {
    prime = true;
  }

  return prime;
}
于 2014-08-13T17:57:59.820 回答
0

好吧,for循环有一些问题。这是代码,

public static boolean checkPrimeNUmber(int number) 
{ 
   if(number <= 1) 
   { 
      return false; 
   } 
   for(int a = 2; a < Math.sqrt(number); a++) 
   { 
      if(number % a == 0) 
      { 
         return false; 
      } 
   } 
   return true;
}
于 2018-04-13T13:46:09.580 回答
0

使用 Java 8 的方式更好更干净

    private static boolean isPrimeA(final int number) {
        return IntStream
               .rangeClosed(2, number/2)
               .noneMatch(i -> number%i == 0);
    }
于 2018-04-23T19:47:22.240 回答