파이썬_실전 프로젝트

프로젝트 오일러 7번문제 - 10001번째 소수

Q-007

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?


10001 번째 소수를 찾는 문제입니다.

 

plan :

무한루프문을 만들고,

prime number 를 확인하는건 앞서 3번문제에서 한적이 있어서 그걸 사용하구요,

루프안에서 소수인지 확인하면서 카운트가 10001번째가 될때 루프를 종료하도록 하면 될거 같습니다.

 

coding:

앞서 3번 문제에서 사용한 소수 확인코드입니다.

def prime_check(number):
    i=1;count=0
    while i<=number:
        if number % i == 0:  #나누어떨어지는 수가 있으면, 
            count=count+1  #매번 카운트 합니다.
        i+=1
    if count==2:
        return True    #그중에서, 카운트가 2일때만 소수라고 true를 줍니다.
    else :
        return False

 이어서 메인 반복문이구요,

i=1;prime_count=0
while True:   #무한루프
    prime = prime_check(i)
    if prime:
        prime_count+=1 #소수가 몇개째인지를 카운트 합니다.
    	print("prime nuber ",i,"count :",prime_count)
    if prime_count==10001:  #10001번째 소수가 되면, 중지합니다.
        break
    i+=1


이렇게 했더니, 작동은 잘되는데, 시간이 너무 오래 걸립니다.
그 이유는, 소수를 확인하는 과정에서, 숫자크기만큼의 루프를 매번 모두 돌도록 했기 때문에, 숫자가 커질수록 점점 더 느려질수 밖에 없습니다.

첫번째 해결책으로는 prime_check()함수를, 나누어떨어질때마다 카운트하는게 아니라, 나누어 떨어지는 즉시 False 를 반환하고 루프를 종료하도록 하면면 짝수들은 그냥 루프 시작하자 마자 i=2일때 바로 종료되고, 홀수들도 소수가 아니면 대부분 초반에 while문이 종료됩니다.

def prime_check(number):
    i=2
    if number==1:   #1은 소수가 아니기 때문에 바로 종료합니다.
        return False
    while i<number:
        if number % i == 0:
            return False  # 나누어떨어지는 수 발견시, 바로 False 를 반환합니다.
        i+=1
    return True

조금 빨라졌지만 그래도 5000 지나면서 다시 느려집니다. 소수가 아니면 곧바로 종료지는데, 소수인경우는 루프문을 끝까지 다 확인해야 알수 있기 때문입니다.
그래서 또 한가지 방법이, 루프를 절반(제곱근까지)만 돌리는 겁니다. 약수는 항상 제곱근을 중심으로 짝으로 존재하기 때문에, 제곱근을 포함하여, 앞쪽만 확인을 하면, 뒷부분은 확인을 안해도 되는 원리입니다.

def prime_check(number):
    if number==1:
        return False
    loop=round(number**0.5)  #제곱근을 계산해서 루프 사이즈를 줄여줍니다.
    i=2
    while i<=loop:  
        if number % i == 0: 
            return False
        i+=1
    return True  # 위 조건에 안걸리고 남는 수는 2,3 두개가 있는데,
                 # 둘다 소수이기 때문에, 마지막에 True를 반환해줍니다.

 

 

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
노마드
현재 버전
선택 버전
graphittie 자세히 보기