7) 10001번째의 소수

http://euler.synap.co.kr/prob_detail.php?id=7

소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.

이 때 10,001번째의 소수를 구하세요.

에라토스테네스의 체 사용

-------------------------------------------------------------------

public static void main(String[] args){

boolean[] sosu = new boolean[10000000];

for(int i=2;i<10000000;i++){

for(int j=i*2;j<10000000;j+=i){

sosu[j]=true;

}

}

int su=0;

for(int i=2;i<10000000;i++){

if(sosu[i]==false){

su+=1;

if(su==10001){

System.out.println(i);

break;

}

}

}

}

다시 공부-----------------------------------------------------------

//짝수중 소수는 2밖에 없으므로 2만 소수로 체크해주고

//다른 짝수는 검사 안하고 건너뛴다.

public static void main(String[] arg){

boolean sosu[] = new boolean[200000]; //false -> 소수, true -> 소수아님

for(int i=4;i<sosu.length;i+=2){

sosu[i]=true;

}

for(int i=3;i<sosu.length;i+=2){

if(sosu[i] == false){

for(int j= i*2;j<sosu.length;j+=i){

sosu[j]=true;

}

}

}

int sum = 1;

for(int i=3;i<sosu.length;i+=2){

if(sosu[i]==false){

sum+=1;

if(sum==10001){

System.out.println(i);

return;

}

}

}

}