素数规划问题

Question

我目前正在开发一个程序，用户在其中输入一个数字，该程序会为您提供不超过该数字的质数个数。虽然没有错误，但程序总是输出相同的数字：3。这是代码：

public static int Prime(int num){
    boolean isPrime = true;
    int count = 0;
    for (int a = 2; a <=num; a++){ 
        for (int i = 2; i <= a/2; i++){
            if (a == 2 || a == 3 || a == 5){
                isPrime = true;
            }
            else if (a % i == 0){
                isPrime = false;
            }
        }
        if (isPrime == true)
            count++;
    }
    return count;
}

Answer 1

在您的内部 for 循环中，您正在设置 isPrime，但随后您继续循环。如果候选除数 i 不能完全除法，则后续循环可能会将 isPrime 设置为 false。只有 2、3 和 5，第一个 if 条件中的 3 个数字，始终将其设置为 true，因此您总是得到 3.

相反，在内部 for 循环开始时将 isPrime 设置为 true，并在每个 for 内部循环之外设置 break您设置的时间 isPrime。如果数字是2、3、5，设置为true和break这样就没有什么可以设置为false，这样就可以数了。如果你找到一个因子，它不是素数，所以设置为 false 和 break 所以没有什么可以将它设置为 true 并且它不被计算在内。

顺便说一下，您的最终 if 条件测试 boolean；可以简化为if (isPrime).

Answer 2

您的策略是通过扫描除自身和 1 以外的因子来测试从 2 到 num 的每个数字是否为素数。这没关系，尽管有点简单，但您的实施严重失败。

一种涉及因素扫描的方法意味着您首先猜测被测试的数字是质数，然后寻找它不是质数的证据。您错过了 "guessing it's prime" 部分，在您的特定代码中，它会在 outer 的开头采用将 isPrime 设置为 true 的形式循环。

另一方面，您的代码在测试 a == 5 的情况后从未将 isPrime 重置为 true。在测试 a == 6 的情况时，该变量将设置为 false，并且在整个持续时间内保持不变。这就是为什么对于任何大于 4 的输入总是得到结果 3 的原因。

如果您在外循环中正确地重置了 isPrime，那么您也可以删除内循环中条件语句的第一部分，因为它是多余的。在 a == 2 和 a == 3 的情况下它无论如何都不会执行，因为在这些情况下内循环执行零迭代。

另请注意，一旦您确定 a 是复合的，并且您运行该循环的迭代次数超过您需要的次数，则从内部循环中断会更有效为素数做（循环直到 i 超过 a 的平方根就足够了；也就是说，直到 i * i > a）。

最后，请注意，通过 Seive of Eratosthenes（或其他素数排序之一）可以更有效地解决此问题，只要您要测试的数字没有大到所需的数组会非常大。

Answer 3

我通过减少检查 a 是 2、3 还是 5 所需的操作次数来简化您的代码。

public static int Prime(int num) {
        int count = 0;
        if (num >= 2) {
            count++; // One optimization here
        }
        for (int a = 3; a <= num; a+=2) {  // Another one here as we don't have any even number except 2 :D
            boolean isPrime = true;
            for (int i = 2; i <= a / 2; i++) {
                if (a % i == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                count++;
            }
        }
        return count;
    }

Answer 4

package basics;

public class CheckPrimeOrNot {
    public void checkprimeNumber(int i){
        int flag=0;

        if(i>2){

            for(int j = 2; j <= i/2; j++){
                if(i%j == 0){
                    System.out.println("Given number is Not Prime");
                    flag=1;
                    break; 
                }
            }
            if(flag==0){
                System.out.println("Given number is Prime");
            }
        } else{
            System.out.println("Please enter a valid number");
        }
    }
    public static void main(String[] args) {
        CheckPrimeOrNot CheckNumber = new CheckPrimeOrNot();
        CheckNumber.checkprimeNumber(11);
        CheckNumber.checkprimeNumber(0);
        CheckNumber.checkprimeNumber(250365);
        CheckNumber.checkprimeNumber(1231);
    }
}

Answer 5

包 com.amit.primenumber;

public class素数{

public static void main(String[] args) {
    long number=23L;
    String message=null;
    PrimeNumber primeNumber = new PrimeNumber();
    boolean result = primeNumber.primeNumber(number);
    if(result){
        message="a Prime Number";
    }else{
        message="Not a Prime Number";
    }

    System.out.println("The given "+number+" number is "+message);
}

public boolean primeNumber(long number){
    for(long i=2;i<=number/2;i++){
        if(number%i==0){
            return false;
        }   
    }
    return true;
}

}

Answer 6

#include <iostream>
using namespace std;


int numberOfPrimes(int num)
{
if(num==2)
  return 1;
else if(num<2)
  return 0;
int prime=1;

for(int i=3;i<=num;i++)
 {
    for(int j=2;j<=(i/2)+1;j++)
     {
        if(i%j==0)
           break;
         if(j==(i/2)+1)
          prime++;

     }

 }
 return prime;
}

素数规划问题

Prime Number Program Problems

java

numbers