소수 구하기 최적의 알고리즘(1)

출처 - http://marobiana.tistory.com/89

한달 전에 면접에서 소수를 손코딩하라는 명을 받았다. (인성면접이라는 훼이크에 당해버렸음 @_@)
소수에 대해서는 깊이 생각해본적이 없었는데..

이번일을 계기로 더더욱 최적의 방법을 생각하는 버릇을 들이겠다는 다짐을 하게되었다.

1. 소수(Prime Number)란 무엇인가?

2, 3, 5, 7, 11, 13, 17....

약수가 1과 자기 자신 뿐인 수이다.

2. 소수를 어떻게 구할까? (알고리즘)

약수가 1과 자신뿐인 것을 확인해야한다.

그러려면??? 

즉, 자기 자신보다 작은 수들을 나누어봐서, 하나라도 나누어지면 소수가 아닌 것이다.

(어떤 수의 배수이면 안된다는 것)

보통은 여기까지만 생각하고 코딩을 시작할 것이다.

그런데 조금만 더 생각해보면 더 좋은 방법이 있다.

일단은 이대로 코딩을 시작해봄 ㄱㄱ

3. 예제

문제 : 특정 숫자를 입력받으면, 그 수 까지의 소수를 모두 출력하기

public static void getPrime(int num) { int i = 2; // i : 나눌 대상 boolean isPrime = true; while (i <= num) { isPrime = true; for (int n = 2; n < i; n++) { if (i % n == 0) { isPrime = false; } continue; } if (isPrime == true) System.out.println(i); i++; } }

num을 i로 나누어봐서 떨어지는 경우가 있다면 소수가 아니다.

이렇게 하면 num만큼 두번 도니까 시간이 많이 걸릴 것이라는 예상이 된다.

반복문을 좀 덜 돌릴 수 있는 방법은???

안쪽 for문을 보면, 0으로 나누어 떨어져서 소수가 아닌 것을 알았을 경우에도 

끝까지 돌면서 굳이 나눠 보고있다.

아래같이 안쪽 for문에 break문 하나를 추가하면, 불필요한 반복을 줄일 수 있다.

for (int n = 2; n < i; n++) { if (i % n == 0) { isPrime = false;                 break; } continue; }

다시 알고리즘으로 돌아와서...

위의 알고리즘은, 

입력 받은 수보다 작은 수들을 나누어보며 떨어지는지 아닌지 판별을 하고 있었다.

조금 더 개선시킨 코드는, 나누어 떨어졌다면 그만 나누어보는 것이었다.

잘 생각해보자.

9는 3의 배수이다. 3은 소수이다.

10은 2의 배수, 5의 배수이다. 2와 5는 소수이다.

14는 2의 배수, 7의 배수이다. 2와 7은 소수이다.

규칙이 보이지 않는가?

다 나누어 볼 필요없이, 입력받은 수보다 작은 수의 소수들만 나누어보면 되는 것이다. 

(ArrayList에 소수를 넣어놓고 나누어보는 방식으로~)

예제 >>

public class PrimeNumber1 { public static void getPrime(int num, ArrayList<Integer> prime) { prime.add(2);  for (int i = 2; i <= num; i++) { for (int j = 0; prime.size() > j; j++) { if (i % prime.get(j) == 0) break; // 소수가 아닌 경우 pass if (j + 1 == prime.size()) // 소수일 때 prime.add(i); } } for (Integer result : prime) { System.out.println(result); } } public static void main(String[] args) { ArrayList<Integer> prime = new ArrayList<Integer>(); long start = System.currentTimeMillis(); getPrime(30000, prime); long end = System.currentTimeMillis(); System.out.println("수행시간 : " + (end - start)); } }

세개의 수행시간 차이를 한번 보자.

50000까지의 소수를 출력한다고 했을 때의 속도 비교이다.

당연한 것이지만 숫자가 커질수록 매우 차이가 난다.

break가 없는 경우 >>

break가 있는 경우 >>

소수만 나누어 본 경우 >>

+ 이것보다 더 최적인 방법이 있으니...

그건 2편에서 계속 ㅋㅋ

http://marobiana.tistory.com/91