Java-为什么这两个在计算 k^2+1 形式的素数时给出不同的输出？

Question

我为我的实验室工作编写了两个程序，用于以两种不同的方式找到小于 1000000 的 k^2 +1 形式的素数，以便在第二个程序中获得更好的时间复杂度，但我在这两个程序中得到的答案不同。有人能告诉我为什么吗？首先，我们首先检查它是否是质数 (n)，然后检查它是否是完全平方数 (n-1)。第二步，我们直接检查 k^2+1 中是否有小于 sqrt(1000000)-1 的 k 并增加计数。但是两者都会产生不同的答案。哪种方法适合计算 1000000 以下的 k^2+1 形式的素数？

第一个程序

 public class KSqPlus1
    {

    public static void main(String [] args)
  { 
     int k = 2;
    for (int n = 11; n < 1000000; n += 2)
       if (isPrime (n))
         if (isPerfectSquare (n - 1))
         {   k ++; 

       }

     System.out.println (k);  

  }

   public static boolean isPrime(int n)
   {
     for(int divisor=3;divisor*divisor<=n;divisor+=2)
         if(n%divisor==0)
           return false;
        return true;
   }
  public static boolean isPerfectSquare (int n)
     {
          for(int divisor=2;divisor*divisor<=n;divisor+=2)
         if(divisor * divisor < n) continue;
          else if (divisor * divisor == n ) return true;
          return false;

     }
 } 

第二个程序

import java.lang.Math;
public class PrimeArrays1
{

  public static void main(String [] args)
  {

    int count=2;int k;
    for(k=3;k<(Math.sqrt(1000000)-1);k++)
    { int x=k*k+1;
     if(isPrime(x))
     {
      count++;

     }
    }
     System.out.println(count);



  }

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

 } 

编辑:下面是正确的 isPrime 函数..现在程序给出相同的答案:)

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

Answer 1

这个方法

  public static boolean isPerfectSquare (int n)
     {
          for(int divisor=2;divisor*divisor<=n;divisor+=2)
         if(divisor * divisor < n) continue;
          else if (divisor * divisor == n ) return true;
          return false;

     }

只有当 n 是偶数的平方时，才会返回 true。我猜您想检查它是否是任何数字的平方。

同理，方法

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

不检查 2 的因数，因此 4、8、... 返回 true。