0

任何人都可以帮助理解这个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？

4

7 回答 7

2

想象一下n可以除以一个k大于的数sqrt(n)。然后你有：

n = k * j

其中j是一个必须小于的数字sqrt(n)（如果两者k和j都大于sqrt(n)则它们的乘积将大于n）。

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

于 2013-06-29T09:03:38.140 回答
1

有问题的行基本上是试图找到作为给定数字的因数的数字（并将它们作为非质数消除）。如果你没有找到给定数的因数，那么你可以说这个数是素数。

就寻找因素而言，您只需要上升到 sqrt(N)，因为如果再上升，您将看到以前已经看到的数字。这是因为每次你找到一个因子时，你实际上找到了两个因子。如果 a 是 N 的因数，则 N/a 和 a 都是 N 的因数。

于 2013-06-29T09:04:44.423 回答
0

如果满足 N = A*B 的唯一整数是 1 和 N（或 N 和 1），则数 N 是素数。

现在要检查一个数 N 是否为素数，我们可以搜索从 2 到 N 的所有 A 和从 2 到 N 的所有 B，看看是否 N=A*B。这将花费 O(N^2) 时间，而且效率非常低。

事实证明，我们只需要将 N 除以一个数，看看是否有余数。这将其降低到 O(N)。

此外，我们不需要从 A=2 一直检查到 A=N。如果 A 大于 sqrt(N)，则 B 必须小于 sqrt(N)。因此我们只需要检查 A 从 2 到 sqrt(N) 以查看 N/A 是否有余数。

于 2013-06-29T09:03:43.943 回答
0

如果我是对的，数学上有一个理论，说几乎所有素数都可以在检查从 2 到 n 的平方根的数字时确定，而不是检查从 2 到 n oder 2 到 n/2 的所有数字。

于 2013-06-29T09:04:40.133 回答
0

一个数的因数只能位于 num 的 1 到 sqrt 之间。因此，我们不是检查从 1 到 num 的因数，而是检查从 1 到 sqrt(num) 的所有数字，看看它们中是否有任何除以 num。如果有任何除以 num，则它不是素数，否则它是。这提高了代码的效率。

于 2013-06-29T09:06:47.097 回答
0

一个快速但肮脏的解决方案..

import java.util.Scanner;

class testing
{
    public static void main(String args[])
    {
        Scanner input = new Scanner(System.in);
        int n, i, j, count = 1;
        System.out.print("How many Numbers ? : ");
        n = input.nextInt();
        for(j = 1;count<=n;j++)
        {

            if(j==1 || j==2)
            {
                System.out.println(j);
                count++;
                continue;
            }
            for(i=2;i<=j/2;i++)
            {
                if(j%i==0)
                    break;
                else if(i == j/2 && j%i != 0)
                {
                    System.out.println(j);
                    count++;
                }  
            }
        }       
    }
}
于 2013-06-29T09:29:13.557 回答
-1 
public class PrimeNumber {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    ArrayList a = new ArrayList();
    for (int i = 1; i <= 100; ++i) {
        if (isPrime(i))
            a.add(i);
    }
    System.out.println("List : " + a);

}

public static boolean isPrime(int value) {
    if (value <= 1)
        return false;


    if ((value % 2) == 0)
        return (value == 2);

    for (int i = 3; i <= value - 1; i++) {
        if (value % i == 0) {
            return false;             
        }
    }     

    return true;
}

}
于 2014-05-02T15:27:12.377 回答