java - 打印素数的程序逻辑

Question

有人可以帮助理解这个java程序吗？

它只是打印素数，当你输入你想要的数量时，它运行良好。

class PrimeNumbers
{      
     public static void main(String args[])       
     {         
       int n, status = 1, num = 3;             
       Scanner in = new Scanner(System.in);

       System.out.println("Enter the number of prime numbers you want");         
       n = in.nextInt();

       if (n >= 1)
       {
         System.out.println("First "+n+" prime numbers are :-");
         System.out.println(2);
       }

       for ( int count = 2 ; count <=n ;  )
       {
         for ( int j = 2 ; j <= Math.sqrt(num) ; j++ )
         {
            if ( num%j == 0 )
            {
               status = 0;
               break;
            }
         }
         if ( status != 0 )
         {
            System.out.println(num);
            count++;
         }
         status = 1;
         num++;
      }         
   }
}

我不明白这个for循环条件

for ( int j = 2 ; j <= Math.sqrt(num) ; j++ )

为什么我们要取 num 的 sqrt...即 3...为什么我们假设它为 3？

Answer 1

想象一下n可以除以数字k大于sqrt(n) 。那么你就有了:

n = k * j

哪里j是一个必须小于 sqrt(n) 的数字(如果 k 和 j 都大于 sqrt(n) 那么它们的乘积将大于 n )。

所以你只需要找到小于或等于 sqrt(n) 的除数即可你可以找到那些大于或等于sqrt(n)的通过简单的划分。在我的示例中，一旦您找到 j ，你可以找到k = n / j .