查找第 10001 个素数 - 代码未返回正确的数字

Question

为了避免任何误解，我是新来的，在Java中还是初学者。我正在尝试编写打印第 10,001 个素数的代码。该代码当前检查数字是否可以被数字 2-9（含）整除，然后检查数字的平方根是否为整数。

public static void main(String[] args){
  Integer Num , Counter;
  Double Sqrt; //square root
  Num=8;
  Counter=4 ;
  while(Counter<10001){
    Num++;
    if ((Num%2!=0) && (Num%3!=0) && (Num%4!=0) && (Num%5!=0) && (Num%6!=0) && (Num%7!=0) &&   (Num%8!=0) && (Num%9!=0)){
    Sqrt = Math.sqrt(Num);    
    if(Sqrt%1!=0){
      Counter++;
     }
   }
 }

 System.out.println(Num); 
 }
}

编辑：

我对其进行了更改，使其不再使用错误的定义，但是使用这个新代码没有输出，我也没有发现循环有任何问题。我也会尝试下面的其他建议，但想知道如何解决这个问题。

 public static void main(String[] args)
   {
 int Num , Counter;
 double Sqrt; //square root
 Num=1;
 Counter=0 ;

 while(Counter<10001){
   Num++;
   Sqrt = Math.sqrt(Num);
   int i = (int)Sqrt;
    while(i>1){
       if(Num%i==0){ //if the number is divisible then the loop is terminated and next number is tested
        i=0;
                   }
        i--;
              }

      if(i==1){
     Counter++;
              }
 }

 System.out.println(Num);   
  }
 }

谢谢。

Answer 1

它不起作用，因为你对质数的定义不正确。

例如，数字 437 不是质数，因为它是 19 * 23，但它会通过您当前的测试。

您的算法需要检查所讨论的数字是否不能被任何个素数整除，直至并包括您正在检查的数字的平方根。

Answer 2

你的逻辑有问题。例如，当检查数字 143 时，您的代码认为它是质数。但是，11*13 = 143，所以它实际上不是质数。我建议创建一个素数列表并在列表中执行 for-each 循环。

List<Integer> primes = new ArrayList<Integer>();
int number = 2;
while (primes.size() < 10001) {
   boolean isPrime = true;
   for (Integer prime : primes) {
      if (number % prime == 0) {
         isPrime = false;
         break;
      }
   }
   if (isPrime) {
      primes.add(number)
   }
   number++;
}
System.out.println(primes.get(10000));

这可能不是一个快速的解决方案，但它应该可以工作...虽然没有测试。祝你好运:).

Answer 3

我会使用基于埃拉托色尼筛法的方法。问题在于，由于您不知道第 10001 个素数是多少，因此您不知道该数组有多大。您可以尝试想一些大数，并希望它大到足以容纳 10001 个素数，但如果它太大，您将需要做额外的工作。可能有一些公式可以帮助您得出一个近似值，然后从那里开始。

另一种方法是从较小的数组开始，然后根据需要扩展它。假设您从一个大小为（比如）1000 的布尔数组开始，代表数字 1 到 1000。执行筛选（从 2 开始；将 2 添加到列表中，标记数组中所有 2 的倍数，找到下一个未标记的值，将其添加到列表中，标记它的所有倍数，等等）。这样显然找不到第10001个素数。因此，当您到达布尔数组的末尾时，将其清除，然后更改 "base" 变量，现在它代表 1001 到 2000 范围内的数字。浏览您已经建立的素数列表, 并标出所有的倍数。现在所有未标记的值都是素数。将它们添加到列表中，清除数组，并更改基数，使数组现在代表 2001 到 3000 之间的数字。遍历素数列表，标记倍数，继续前进，直到列表大小达到 10001。

我不知道这种方法与其他方法相比效率如何，但直觉上它似乎比一个一个地检查所有数字并检查每个数字的除数要好。

Answer 4

您的新版本不起作用，因为您正在测试从 Math.sqrt(Num) 到 1 的所有数字，而不是从 2 到 1 的所有数字。1 总是准确地进入每个数字，因此您的程序不会认为任何数字都是质数，并且永远存在。

要使其正常工作，您需要将 while(i>0) 更改为 while(i>1)。您还需要将 if(i==0) 更改为 if(i==1)。我也不确定为什么 Num 和 Counter 的值是 8 和 4。我会让你弄清楚它们应该是什么。

Answer 5

在这里，您会发现另一种（紧凑的）方式来生成由 const MAX（生成的元素数）限制的素数序列，使用 Stream class（对于生成的每个 x，过滤器拒绝只能被 x 整除的 x：一个只能被其自身整除且 1 为质数的数）：

public class PrimeNumbersSeq {

    final private static Long MAX=10001l;

    public static void main(String[] args) {
    System.out.println(LongStream
            .iterate(2, x -> x + 1)
            .filter((i) -> LongStream.range(2, i)
            .noneMatch(j -> i % j == 0)).limit(MAX)
            .mapToObj(String::valueOf)
            .collect(Collectors.joining(",", "[", "]")));
    }
}

输出：[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73, 79,83,89,97,101...

查找第 10001 个素数 - 代码未返回正确的数字

Finding the 10001st Prime Number - Code not returning correct number

java

numbers