티스토리 뷰

공부자료

[프로젝트오일러] 7번-10,001번째 소수

임다솜 임다솜 2016.09.26 18:00

Project Euler

프로젝트 오일러

 

Problem 7

10,001번째 소수 구하기

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

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


Hint

에라토스테네스의 체 응용하기!


소수는 다른 소수로 나누어지지 않는다.

예를 들어 25라는 숫자가 소수인지 알고 싶다면

2~25 사이의 소수로 나누어보면된다.

2, 3, 4, 5, 6, ... 25 이렇게 모든 수로 나누어 볼 필요가 없다.

2, 3, 5? 5로 나누어지므로 25는 소수가 아니다.


반면 29라는 숫자가 소수인지 알아보면

2~29 사이의 소수는  2, 3, 5, 7, 11, 13, 17, 19, 23이다.

29는 이 모든 소수로 나누어 떨어지지 않기 때문에 소수이다.


그렇다면, 찾은 소수는 배열에 추가하여 다음 숫자를 판별하는데 사용하면 된다.

30이라는 숫자가 소수인지 알아보려면 소수배열에 있는 소수만 반복하여 나누어보면된다.



Answer

getPrimeNubmerAt은 RESULT_INDEX번째 소수를 리턴하는 함수입니다.

// RESULT_INDEX = 인덱스 변수가 많아서 헷갈릴 수 있어 final로 선언.
public static int getPrimeNumberAt(final int RESULT_INDEX){
// int COUNTER = 0; // COUNTER = 반복문을 몇 번 돌았는지 확인하기 위해 선언.

int[] primeArr = new int[RESULT_INDEX];
primeArr[0] = 2; //첫번째 소수 2는 직접 입력한다.
int primeArrIndex = 1; //첫번째 소수 2를 가리키도록 한다.

// normalNumber는 1, 2, 3, 4, ... 로 증가하는 검사 대상이 되는 모든 숫자이다.
// RESULT_INDEX번째 소수가 무엇인지 모르기 때문에 계속 1씩 증가하여 검사한다.
int normalNumber = 3;

// 소수를 저장한 배열의 인덱스가 10001이 될때까지 계속 소수를 찾는다.
while(primeArrIndex < RESULT_INDEX){

int tempIndex = 0;
while(true){
//COUNTER++;

// i가 증가되어서 arr의 길이와 같아지면

// 모든 소수로도 나누어지지 않는다는 뜻이므로 소수로 판별한다.
if(tempIndex == primeArrIndex){
int primeNumber = normalNumber;
primeArr[primeArrIndex++] = primeNumber;
break;
}

// 나누어 떨어지면 소수가 아니다. 즉 나머지가 0이 아니면 소수이다.
int remainder = normalNumber % primeArr[tempIndex];
if(remainder == 0){
break;
}else{
tempIndex++;
}
}
normalNumber++;
}
//System.out.println("my case's COUNTER = "+COUNTER++);
return primeArr[primeArr.length-1]; //마지막 인덱스의 수가 RESULT_INDEX번째 소수이다.
}



Other Answer

다른 분들이 하신 코드를 보고 따라해보았는데요.

제가 한게 가장 빠르더라구요!

코드는 제가 만든 것보다 간결하고 단순하지만 그만큼 반복문을 오래 돌고 시간도 오래 걸립니다.

public static int case2(){
int i = 2;
int num = 0;
int COUNTER = 0; //반복문 출력하기 위해 선언.
while(true){
int cnt = 0;
for (int j = 2; j <= i; j++) {
COUNTER++;
if(i%j == 0){
cnt++;
}
}
if(cnt==1){
num++;
}
if(num==10001){
//반복문을 몇 번 돌았는지 출력.
System.out.println("case2's COUNTER = "+COUNTER);
return i;
}
i++;
}
}


또 다른 방법인데요. 이것도 코드가 비교적 간결하지만 시간이 오래걸립니다.

public static int case3(){
int COUNTER = 0;

int prime = 2;

int count = 1;
boolean isPrime = true;

while(true){
isPrime = true;

for(int n=2; n<prime; n++){
COUNTER++;

if(prime%n==0){
isPrime = false;
break;
}
continue;
}

if(isPrime){
count++;
if(count==10002){
System.out.println("case3's COUNTER = "+COUNTER);
return prime;
}
}

prime++;
}
}


제가 만든 코드와 case2(), case3()의 COUNTER(반복문)횟수를 출력해보면!

public static void main(String[] args){
System.out.println(getPrimeNumberAt(10001));
System.out.println(case2());
System.out.println(case3());
}


다음과 같은 결과가 나옵니다!

제가 만든 케이스는 50,348,515번 반복문을 돌구요.

case2는 1,190,528,357

case3은 497,111,968번 반복문을 돌게 됩니다!

// my case's COUNTER = 50348515
// 104743

// case2's COUNTER = 1190528357
// 104743

// case3's COUNTER = 497111968
// 104743









댓글
  • 프로필사진 ㅁㄴㅇㄹ from math import *

    loop=0
    count=1
    num=1
    lis=[2]
    while(count!=10001):
    dividable = False
    num+=2
    for i in lis :
    loop+=1

    if(i>sqrt(num)):
    break

    if(num%i==0) :
    dividable = True
    break

    if not dividable :
    lis.append(num)
    count+=1

    print("10001번째 소수 {0}, {1}번 실행".format(num,loop))

    결과 : 10001번째 소수 104743, 746495번 실행

    python이긴 합니다만, 에라토스테네스의 접근을 사용하면 약수를 제곱근까지만 체크해도 괜찮아서 실행시간과 반복횟수를 줄일 수 있습니다~
    2017.10.09 18:51 신고
댓글쓰기 폼
공지사항
Total
41,170
Today
70
Yesterday
59
링크
TAG
more
«   2018/07   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
글 보관함