Java函数查找质数不起作用

Question

这个函数需要输入一个整数N。该函数必须打印出2到N（包括N本身，如果N是质数）之间的所有质数。

我有这个函数并且它可以运行，但是它会跳过一些质数甚至包括一些偶数，例如8。我似乎找不到导致这种情况的错误。

以下是我的代码：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class PrimeNumbers {

    List <Integer> primeList = new ArrayList<Integer>();
    public ArrayList<Integer> findPrimes(int n){

        if(n == 2){
            primeList.add(n);
        }
        else{
            //should I have i=i+2 instead of i++ to move faster? 
           //If so, by doing this, it causes weird and different 
          //output when running
            for(int i=2; i<=n; i++){
                if(n%i != 0){
                    primeList.add(i);
                }
            }

        }

        return (ArrayList<Integer>) primeList;
    }

    public static void main(String[] args) {
        PrimeNumbers pn = new PrimeNumbers();

        System.out.println(pn.findPrimes(15));
    }

}

- Ebad Saghar

---

你的逻辑存在问题，你只是从2到n迭代一次，但是你应该有一个函数来检查数字是素数还是合数，并在循环内调用该函数。 - Mohammad Ashfaq

创建一个函数，用于检查数字是否为质数，并返回布尔值true或false。在循环中通过传递循环计数器作为参数调用该函数，如果函数返回true，则将该数字添加到数组列表中。 - Mohammad Ashfaq

你的算法不正确。你必须检查每个“i”是否为质数，但你检查的是“n”是否被每个“i”整除。向谷歌询问“素数筛法”，你会得到一个高效且可行的算法。 - linluk

只需要在纸上计算两个数字，你就会明白你所做的与质数完全无关。你所做的只是找到了n的所有非因子。 - Michael Yaworski

@mikeyaworsk 我知道逻辑是错误的，我需要改变它。但是它甚至没有找到N的因数，因为当我传入15时，得到的数字是4和8。 - Ebad Saghar

Answer 1

你的逻辑完全错误。只有在测试了所有可能的除数后，才能说一个数字是质数。你目前正在添加任何余数不为零的数字，这是错误的。余数不为零意味着它不能被整除，也就是说它不是你正在测试的因数的倍数，例如：

8 % 3 -> 2
2 != 0 -> true
therefore 8 is prime

只有在完成循环并且没有测试返回true后，才能执行您的.add()调用：

is_prime = true; // assume prime
for(i = 2; i <= n; i++) {
     if (n % 2 == 0) { // no remainder, even divisible, therefore NOT primt
         is_prime = false;
         break; // abort the loop, no point in testing more
     }
}

是的，您可以通过从3开始测试并跳跃2来提高效率。由于2是唯一的偶数质数，因此其他任何偶数都不可能是质数，因为2是所有偶数的因子。因此测试3、5、7、9等。

例如：

  test if `n` is even and `!= 2` - if so, then it's NOT prime
  run 3,5,7,... loop to test everything else

- Marc B

Answer 2

您寻找质数的逻辑是错误的。

目前，您的代码所做的是： 1. 迭代所有小于N的整数 2. 找到任何N不能被除的整数，并将它们添加到列表中。 这与质数无关。

相反，您的代码应该做以下事情： 1. 迭代所有小于N的整数 2. 对于每个这些整数（假设为M），运行一个子循环迭代其下方的所有整数，并检查是否没有这些整数可以被M整除。 如果子循环在未找到M的因子的情况下完成，则将M添加到列表中-它是质数（除了1和它本身外不能被任何整数整除）。

检查数字（2或以上）是否为质数的简单代码：

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

    return true;
}

有很多优化方法，这是一个独立的世界。

- SirKnigget

---

你能提供一小段代码来演示这个吗？ - Ebad Saghar

Answer 3

您所做的只是找到了n的非因数。通过将它们相加，测试在其之前的每个数字是否是n的因数。
您需要做的是从2到n遍历每个数字，并测试它是否为质数。您需要两个循环。我建议创建一个确定质数的方法，您当前的方法应该是可以使用的。只需将if (n % i != 0)替换为if(isPrime(i))。

public static boolean isPrime(long n) {
    // eliminate the simple cases
    if (n < 2) {
        return false;
    } else if (n == 2) {
        return true;
    }

    // only test up until the square root of that number
    for (int i = 2; i < Math.pow(n, 0.5) + 1; i++) {
        if (n % i == 0) {
            return false; // found a factor, it's not prime
        }
    }
    return true; // hasn't found a factor and returned false, so it's prime
}

然后在您当前的代码中：

for(int i=2; i<=n; i++){
    if(n%i != 0){
        primeList.add(i);
    }
}

只需将 if(n%i != 0){ 改为 if(isPrime(i))

代码如下:

for(int i=2; i<=n; i++){
    if(isPrime(i)) {
        primeList.add(i);
    }
}

- Michael Yaworski