[알고리즘] 소수 구하기

By | 2015/10/23

요즘 코딩 감각이 좀 둔해진 것 같아서, 다시 프로젝트 오일러 정주행중인데, 예전에 처음 풀었을 때에는 그냥 뺑뺑이 돌려서 소수를 구했었다.

이번에는 두번째 하는거라서 자료를 조금 찾아보기도 하고, 나름 생각해서 이렇게 하면 빠르겠다
싶은 것도 만들어보기도 하였다…

결과적으로는 수학을 이용한 것이 제일 빨랐다..

첫번째 메서드 실행결과

elapsed time : 0:03:00.578463
method1 DONE!

두번째 메서드 실행결과

elapsed time : 0:00:00.272193
method2 DONE!

세번째 메서드 실행결과

elapsed time :  0:00:00.305218
method3 DONE!

아래는 작성해본 코드이다.

[gfm]
“`
from datetime import datetime

def timer(method):
def timed(*args, **kwargs):
start = datetime.now()
result = method(*args, **kwargs)
end = datetime.now()

print (“elapsed time : “, end – start)
return result

return timed

### 정의대로 만든거
def isPrime(x):
if x == 1:
return False
else:
for num in list(range(2,x)):
if x % num == 0:
return False
return True

### 약간의 수학을 이용
### x 가 a와 b의 곱으로 이루어진다면 a와 b의 최대값은 x**0.5 보다 작거나 같아야 한다. 는 원리를 이용
def isPrime2(x):
if x == 2 or x == 3: return True
if x%2 == 0 or x < 2 : return False for i in range(3, int(x**0.5) + 1, 2): if x%i == 0: return False return True ### 인터넷에서 본거 def isPrime3(n): if n < 2: return False if n % 2 == 0: return n == 2 k = 3 while k * k <= n: if n % k == 0: return False k += 2 return True @timer def execute1(size=1000): prime_list = [] for x in list(range(2, size)): if isPrime(x): prime_list.append(x) print("method1 DONE!") print(prime_list) @timer def execute2(size=1000): prime_list = [] for x in list(range(2, size)): if isPrime2(x): prime_list.append(x) print("method2 DONE!") print(prime_list) @timer def execute3(size=1000): prime_list = [] for x in list(range(2, size)): if isPrime3(x): prime_list.append(x) print("method3 DONE!") print(prime_list) if __name__ == '__main__': num = 100000 execute1(num) execute2(num) execute3(num) pass ``` [/gfm]