java - Use Modulus Operator to Get Prime Numbers

Question

How would you modify the below to print out all prime numbers from 1-100? The below has an issue with the number 2 coming back as not prime. The if(i%number == 0) condition is met for the number 2 as 2%2 is returned as 0.

public class Test {

    /**
     * @param args
     */
    public static void main(String[] args) {
        for(int i=1; i<=100; i++){
            if(isPrime(i)){
                System.out.println(i + " is a prime number");
            }else{
                System.out.println(i + " is not a prime number");
            }
        }

    }
    public static boolean isPrime(int number){
        for(int i=2; i<=number; i++){

            if(i%number == 0){
                return false;
            }else{
                return true;
            }
        }
        return false;
    }

}

score 2 · Accepted Answer

 i<=number

您不应该检查该数字是否可以自行整除。

你还有另一个问题：

        }else{
            return true;
        }

一旦找到一个不可整除的数字，您就会返回 true，即使它稍后确实有因数。

score 2 · Accepted Answer

这是一种用于确定数字是否为素数的算法。

数字是否小于 2？如果是，则返回 false。
数字是2还是3？如果是，则返回 true。
数字是4吗？如果是，则返回 false。
取数字的平方根，四舍五入到下一个整数。这对于小素数是可选的，但可以加快确定大数的速度。
从 5 循环到数字（或数字）的平方根，以 2 递增。
- 将循环数除以到目前为止确定的素数。
- 如果除法的模数为零，则返回 false。
如果循环完成，则返回 true。

score 1 · Accepted Answer

这将起作用。2 是测试素数时的一种特殊情况。如果你开始搜索一个越来越大的...你可能想看看eratosphenes的筛子。

每个素数都是另一个数的倍数。以3为例。使用筛子，如果您发现 3 是素数，它将“忽略”所有 3 的倍数，从而减少查找后续素数所需的时间。它加快了速度......很多:)

 public class JavaApplication47 {

 public static void main(String[] args) {

    for(int i=1; i<=100; i++){
        if(isPrime(i)){
            System.out.println(i + " is a prime number");
        }else{
//                System.out.println(i + " is not a prime number");
        }
    }
}

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

筛选示例 - 未实施 - 可用于参考和理解。

static boolean [] allPrimes = new boolean[10000];

public static void fillTheSieve(){
    Arrays.fill(allPrimes, true);
    allPrimes[0] = allPrimes[1] = false; //1 and 0 are false. winning

    for (int i = 2; i < allPrimes.length; i++) {
        //check if prime, if so getmultiples and declae false
        if(allPrimes[i]){
            for (int j = 2; i*j<allPrimes.length; j++) {
                allPrimes[i*j] = false;

            }
        }

    }
}

score 1 · Accepted Answer

你这里有几个问题。首先，在检查一个数字是否为素数时，永远不要检查每个数字，直到检查素数的实际数字。检查直到数字的平方根的所有素数总是足够的。

要修复该错误，请查看您的 for 循环条件并相应地对其进行编辑：

for(int i=2; i<=number; i++)

其次，当函数返回时，它会停止。目前使用您的 if/else 语句：

if (i%number == 0) {
   return false;
} else {
   return true;
}

如果这个条件即使在 else 语句返回 true 时也转到 else 语句，你要确保只有在检查了所有想要检查的数字后才真正返回 true。

此外，我认为您没有仔细考虑过您的基本情况。您在最后一行中所说的是，如果以前所有内容都从裂缝中溜走，那么它应该假定该数字不是素数。想一想，我相信你会想出来的。

score 0 · Accepted Answer

与 Prime 打交道时只需考虑几件事。您可以在开始时为 2 设置一个特殊情况（即类似if(number == 2)...）。

除了您错误地一直检查以 i<=number仅考虑您需要走多远才能确定它不是素数之外，已经给出了提示i*i或Math.sqrt

增量中的另一件事是i++考虑这意味着什么，我意识到这仅适用于前 100 个素数，但您应该始终考虑性能。你真的必须检查所有数字（2,3,4,5,6...）（提示：如果你检查了它是否可以被 2 整除，那么你不需要检查 4,6,8 等......）

最后，在您的 return 语句中，考虑使用一个boolean标志，仅当您确定该数字是质数或不是质数时，您才将其设置为 false/ true。而且您只需要使用 1 个 return 语句。

希望有帮助。

score 0 · Accepted Answer

素数的定义明确指出不能是素数。

这意味着isPrime(1)应该返回false。你的实现是做什么的。

但isPrime(2)应该返回true。您的实施没有。这不是因为(2 % 2 == 0)您正在检查从 2 到 N 的所有数字，而不是从 2 到 N-1。最后一个数字 N 将始终产生零余数(N % N == 0)

score -4 · Accepted Answer

请试试这个

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

java - Use Modulus Operator to Get Prime Numbers

7 回答 7

Related

Reference