正在改进第10001个素数项目

Question

我一直在研究Euler项目问题​​，该问题是找到第10001个素数。我用Java创建了项目，它给了我正确的答案。我忍不住注意到它花了17秒才能找到答案。我对Java还是很陌生，并且希望得到有关如何提高Java程序效率的反馈-目前它是蛮力的。

static boolean isPrime;  
static int primeCount;  
static int forI = 1;  
static int latestPrime;  

public static void main(String[] args){  
    long startTime = System.currentTimeMillis();  
    while(primeCount < 10001){  
        isPrime = true;  
        forI++;  
        for(int i = forI - 1; i > 1; i--){  
            //If forI is divisible by another number < forI, it is not prime  
            if(forI % i == 0){  
                isPrime = false;  
            }  
        }  
        if(isPrime){  
            primeCount++;  
            latestPrime = forI;  
        }  
    }  
    long endTime = System.currentTimeMillis() - startTime;  
    System.out.println(primeCount+" "+latestPrime);  
    System.out.println("Time taken: " + endTime / 1000 + " seconds");  
}  

Answer 1

您将要签出Sieve of Eratosthenes。

基本上，对于每个数字，您通过检查每个数字是否小于其平均数来检查其质数，效率非常低。

为了方便进行改进，您只需要检查所有小于该数字的平方根的除数。

Answer 2

import java.util.Scanner;
public class NewNthPrime{
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        boolean flag = false;
        int max = 10002;
        int[] a = new int[max];
        a[0] = 2;
        int i = 3,j=0;
        int t = in.nextInt();
        for(int a0 = 0; a0 < t; a0++){
            int n = in.nextInt();
            while(j<n){
                for(int y=0;y<a.length;y++){
                    if(a[y]==0){
                        break;
                    }
                    else if (i%a[y]==0){
                        flag = true;
                        break;
                    }
                }
                if(!flag){
                    a[++j]=i;
                }
                flag =false;
                i+=2;
            }
            System.out.println(a[n-1]);
        }
    }
}