By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10 001st prime number?
10001번째 소수는 무엇인지 찾는 문제이다.
일단 소수를 판별하는 메소드를 하나 만들고,
10001번째 소수가 결과로 나오면 출력한다.
소수인지 아닌지 판별하는 메소드가 핵심 포인트.
public class ProjectEuler7 {
private static boolean isPrime(long n){
if ((n % 2 == 0)&&(n != 2))
return false; // 2를 제외한 짝수는 소수가 아니다.
for (long i = 3; i <= (n^(1/2)+1); i += 2){ // 증감수=2:모든 짝수는 검사에서 제외 & root n + 1 까지만 검사하여 시간 단축
if (n % i == 0)
return false; //not prime
}
return true;
}
public static void main(String args[]){
// long begin = System.currentTimeMillis();
int NumPrimes = 1; // 몇번째를 의미
long i = 2; // 첫번째 소수
while(true){
if (isPrime(i)){
if(NumPrimes==10001){
System.out.println(i);
}
i++;
NumPrimes++;
}else{
i++;
}
}
// long end = System.currentTimeMillis();
// System.out.println(end-begin + "ms");
}
}
주석 처리된 부분은 수행 시간을 알아보기 위해 잠깐 사용한 부분.
반응형