소수 알고리즘
중학교 때 소수란 것을 배웠을 것이다. 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수로 정의된다. 예를들면 2, 3, 5, 7, 11, 13…이 소수이다. 2는 유일한 짝수 소수이다. 소수를 구하는 방법들을 하나씩 알아보자.
1. N보다 작은 수로 나누어본다.
가장 생각하기 쉬운 방법이다. 소수의 성질을 이용하여, N을 2부터 N-1까지 모두 나누어 보는 것이다. 나누어 떨어지는 수가 존재하지 않으면 N은 소수이다.
1 2 3 4 5 6 7 8 | def getPrime(number): #number가 소수이면 출력하는 함수 if number == 2: #2는 소수이므로 바로 출력 print number, for x in range(2,number): #2부터 number-1까지 나누어 본다 if number % x == 0: #나누어 떨어지면 소수가 아니므로 break break elif x == number - 1: #number-1까지 나누어지지 않으면 소수 print number, | cs |
파이썬으로 소수를 구하는 함수를 짜보았다. 가장 이해하기 쉬운 방법이지만, N에 큰수가 들어가면 가장 오래 걸리는 알고리즘이다.
2. N을 2부터 sqrt(N)까지 나누어본다.
위에 방법보다 좀 더 효율적인 방법이다. N=a*b 형태로 나타낼 수 있다. 이 때, a와 b는 둘다 1보다 큰 정수이다. a와 b 둘 중 하나는 sqrt(N)보다 작거나 같다. 그러므로 N을 2부터 sqrt(N)까지 나눠서 나누어지지 않으면 소수이다.
1 2 3 4 5 6 7 8 9 10 11 | import math def getPrime(number): #number가 소수이면 출력하는 함수 if number == 2: #2는 소수이므로 바로 출력 print number, for x in range(2,number): #2부터 number-1까지 나누어 본다 if number % x == 0: #나누어 떨어지면 소수가 아니므로 break break elif (x > math.sqrt(number)): #sqrt(number)까지 나누어지지 않으면 소수 print number, break | cs |
for문으로 N보다 작은 수로 나눌 때, sqrt(N)까지 나눠서 소수여부를 판별하므로 N까지 나누는 첫 번째 방법보다 빠르다.
3. N을 N보다 작은 소수로만 나누어본다.
중학교 때, 소인수분해라는 것을 배웠을 것이다. 이 개념을 이용하는 것이다. 소수가 아닌 수는 N보다 작은 소수로 나누어진다.
12를 예를 들어보자. 12의 약수는 1,2,3,4,6,12이다. 약수 중 소수인 것이 소인수이다. 12의 소인수는 2,3이다. 12는 12의 소인수들의 곱으로 표현할 수 있다. 이렇게 표현하는 것이 소인수분해다. 12는 2^2*3라고 소인수분해 할 수 있다.
즉, 소수가 아닌 수는 N보다 작은 소수로 나누어진다는 것을 알 수 있다. 소인수분해에 대해서 좀 더 알고 싶은 분들은 이 블로그를 참고하면 좋을 것이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | import math def getPrime(number): primeList = [2] #소수 리스트 생성 num = 3 #3부터 소수인지 검사한다 while (num <= number): for x in primeList: if(num % x == 0): #소수로 나누었을 때 나누어지면 소수아님 break elif(x == primeList[-1]): #소수리스트의 끝원소로도 나누어지지 않으면 소수 primeList.append(num) #구한 소수를 소수리스트에 추가 break num += 1 if(number in primeList): #number가 소수리스트에 존재하면 소수인 것이므로 print number | cs |
마찬가지로 파이썬으로 구현해보았다. 첫 번째 방법보다 적은 수를 나누므로 더 빠르다.
끝으로
위에 3가지 방법을 살펴보았다. 실제로 코딩을 한 뒤, 10만 이상의 큰 수를 넣어보면 실행 차이가 많이 나는 것을 알 수 있을 것이다. 2번과 3번 방법을 혼합하여 더 빠른 알고리즘을 만드는 것도 가능하다.
사실 가장 효율적인 소수 찾는 알고리즘은 에라토스테네스의 체(Sieve of Eratosthenes)방법이 있다. 이 방법에 대해서는 추후에 포스팅할 예정이다.
참고
'programming' 카테고리의 다른 글
| [안드로이드]Android SDK version (0) | 2015.11.05 |
|---|---|
| [안드로이드]프로세스와 스레드 (0) | 2015.11.04 |
| 소프트웨어 공학이란? (0) | 2015.11.01 |
| Android SDK란? (0) | 2015.10.29 |
| Platform과 Framework의 차이는? (2) | 2015.10.29 |