파이썬_실전 프로젝트

프로젝트 오일러 3번문제 - 가장큰 소인수

어떤 숫자의 가장큰 소인수를 구하는 문제입니다.
쉬운방법은 소인수 분해 공식을 사용하는 것이고, 좀 어려운 방법은 약수와 소수를 일일이 다 확인하면서 찾는방법입니다.
 

Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

 

방법 1 : 소인수 분해
def prime_factor(num):
    factor=2
    while not num == 1:
        if num%factor == 0:
            print(num,factor)
            num = num/factor
        else:
            factor+=1
    return factor

number = 600851475143
print(prime_factor(number))
600851475143 71
8462696833.0 839
10086647.0 1471
6857.0 6857
6857

나누는 수(factor)를 계속 증가시키면서 원래수를 나누어떨어질때마다 나누어서 크기를 줄여나갑니다. 원래수가 최종적으로 1이되면, 그때의나누는 수(factor)가 prime_factor 가 됩니다.

 

방법 2 : Brute force (원초적으로!?)

두번째 방법은 모든수로 나누어 보면서 일일이 약수와 소수를 확인하는 방법입니다. 귀찮기도 하고, 계산속도가 느릴수도 있는데, 딱히 방법이 생각이 안날때는 이렇게라도 풀어야죠. 아니면 코드 연습삼아 brute force 로 풀어보는것도 괜찮을거 같습니다.

 

약수 구하기
number = 50
for i in range(1,number+1):
    if number%i==0:  #나눠서 0이면 약수 
        print(i)
1
2
5
10
25
50

 

 소인수 확인
def is_prime(num):
    if num==1:    # 1은 소수가 아니므로 False
        return False
    i=2
    while i<num:
        if num%i==0: # 나누어 떨어지는 수가 하나라도 있으면 False
            return False
        i+=1
    return True 

number = 1000
i=1
while i <= number:
    if number%i==0:
        print(i,is_prime(i))
    i+=1
1 False
2 True
4 False
5 True
8 False
10 False
20 False
25 False
40 False
50 False
100 False
125 False
200 False
250 False
500 False
1000 False

 

결과
def is_prime(num):
    if num==1:
        return False
    i=2
    while i<num:
        if num%i==0:
            return False
        i+=1
    return True

number = 600851475143
for i in range(1,number+1):
    if number%i==0 and isPrime(i):
        print(i,"is prime factor")
71 is prime factor
839 is prime factor
1471 is prime factor
6857 is prime factor
 
---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
<ipython-input-9-70c1bc7167a6> in <module>()
     13 number = 600851475143
     14 for i in range(1,number+1):
---> 15     if number%i==0 and isPrime(i):
     16         print(i,"is prime factor")

현재 두번째 방법으로 완성된 코드의 문제점은 시간이 너무 오래걸린다는 점입니다. 그냥 오래걸리는게 아니라, 숫자가 커질수록 점점더 느려집니다. 소수 확인하는 is_prime() 함수를 좀 개선을 해야할것 같습니다.

 

개선

 약수를 찾는 부분에서는, 약수는 제곱근을 중심으로 항상 짝으로 존재하기 때문에, 제곱근 앞부분의 약수를 찾으면, 제곱근 뒤에 있는 약수는 앞에서 찾은 약수로 원래숫자를 나누어서 구할수 있습니다.

또 소수확인도 위에서 설명한 것과 같은 원리로, 제곱근까지만 약수가 없는것을 확인하면 그 뒷부분은 확인을 할필요가 없기 때문에, 루프를 제곱근까지만으로 줄여주도록 하겠습니다.

 

def is_prime(num):
    if num==1:
        return False
    loop=num**0.5 # 루프사이즈를 제곱근으로 축소
    i=2
    while i<=loop:
        if num%i==0:
            return False
        i+=1
    return True

number = 600851475143
loop = number**0.5 # 약수를 확인하는 부분도 제곱근으로 축소
i=1
while i <= loop:
    if number%i==0:
        number2=number/i
        print(i,number2,end=' ')
        if is_prime(i):
            print(i,"is prime factor")
        elif is_prime(number2):
            print(number2,"is prime factor")
        print("")
    i+=1
1 600851475143.0 
71 8462696833.0 71 is prime factor

839 716151937.0 839 is prime factor

1471 408464633.0 1471 is prime factor

6857 87625999.0 6857 is prime factor

59569 10086647.0 
104441 5753023.0 
486847 1234169.0

댓글

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