[알고리즘] 소수 구하기

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!

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

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