600851475143 이 숫자의 소인수중 가장큰 수를 찾는 문제입니다.
간단한 방법은 수학공식인 소인수 분해 공식을 사용하는 방법이 있고, 직관적으로는 약수와 소수를 일일이 다 확인하면서 찾는방법이 있습니다.
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
초등학교인가 중학교인가에서 배웠었나요? 그 소인수 분해 방법입니다. 2부터 시작해서 나누어지는 수가 1이 될때까지 계속 나누어 가는 방법입니다. 코드상으로는 나누는 수(factor)를 1씩 증가시키면서 원래수를 나누어 떨어질때마다 나누어서 크기를 줄여나갑니다. 원래수가 최종적으로 1이되면, 그때의 나눈 수(factor)가 가장큰 소인수(prime_factor) 가 됩니다. 프로그래밍이라기보다는 수학적인 해결방법에 가깝겠네요.
방법 2 : Brute force (원초적으로!?)
두번째 방법은 숫자크기만큼의 루프를 돌면서, 매 루프마다 또다시 그 수만큼의 하위루프를 돌면서 모든수로 나누어 보고 나누어 떨어지면(=약수가 있으면) 그 약수가 다시 소수인지를 확인하는 방법입니다. 루프를 2중 3중으로 돌기때문에 계산속도가 느릴수 있는데, 적당한 방법이 생각이 안날때 쓸수 있는 만능(?)의 방법입니다. 단, 루프를 잘못 만들거나 연산속도가 느리면, 계산이 끝이 안나는 사태가 발생할수도 있습니다;; 첫번째 방법보다는 컴퓨팅적인(?) 해결방법에 가까워서, 코드 연습삼아 brute force 로 풀어보는것도 좋습니다.
약수 확인
number = 50
for i in range(1,number+1):
if number%i==0: #나눠서 0이면 약수
print(i)
1 2 5 10 25 50
약수는 나누어봐서 나머지가 0이면 약수입니다.
소수 확인
#소수 확인
number = 50
i=1
while i <= number:
if number%i==0:
print("not prime")
break
i+=1
not prime
어떤숫자가 소수인지를 확인하는 과정은 약수확인과 비슷합니다. 나누어떨어지는 수가 하나라도 있으면, 소수가 아닌것이고, 나머지 루프는 확인할 필요없이 바로 중지시키면 됩니다.
위 코드를 함수로 만들어서 소수인지에 따라 True/False 만 반환해주도록 하겠습니다.
#소수 확인 함수
def is_prime(num):
if num==1:
return False # 1은 소수가 아니므로 False 반환
i=2
while i<num:
if num%i==0: #나누어 떨어지는 수가 있으면
return False # 바로 False를 리턴하고 함수를 종료합니다.
i+=1
return True
number = 10000
if is_prime(number):
print("prime")
else:
print("not prime")
not prime
이제 위의 약수 코드와 소수코드를 합쳐서 약수를 찾을때마다 그 약수를 소수확인 함수에다가 넣어서 소수인지를 확인하면 되는데, 계산이 되는지, 한번 실행해 보세요.
#합친 코드
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 = 82385683
i=1
while i <= number:
if number%i==0 and is_prime(i):
print(i,"is prime factor")
i+=1
숫자크기를 천만정도까지 주면 아마 계산이 그럭저럭 결과가 나올건데, 억단위가 넘어가면 시간이 어마어마하게 걸립니다. 심지어 우리가 계산해야하는 수는 6000 억입니다,,
속도 개선
보통 루프문을 쓰는 프로그래밍에서 속도가 느린 이유는 중복계산을 하기때문입니다. 그래서 어디서 중복이 발생하는지를 찾아내야 합니다. 굳이 할필요가 없는 계산을 줄여주는거죠.
이 문제에서 약수를 찾는 부분에서는, 숫자 크기만큼의 모든 루프를 다 조사할 필요없이, 약수는 제곱근을 중심으로 짝으로 존재하기 때문에, 제곱근 앞부분의 약수를 찾으면, 제곱근 뒤에 있는 약수는 앞에서 찾은 약수로 원래숫자를 나누어서 구할수 있습니다.
또 소수확인도, 짝수의 경우에는 2로 나누자 마자 소수가 아닌것을 바로 알수 있지만, 홀수이면서 크기가 큰 숫자는 그 숫자크기만큼 다 나누어 봐야 약수가 없다는걸 알수있는데, 이경우도 같은 원리로 제곱근까지만 약수가 없는것을 확인하면 그 뒷부분은 확인을 할필요가 없기 때문에, 루프를 제곱근까지만 줄여도 같은 결과가 나옵니다.
제곱근이 루프의 중간보다 훨씬 앞에 있기도 하고, 또 제곱근 이후의 숫자들은 크기 때문에, 이정도만 해도 루프의 크기를 엄청나게 줄일수 있습니다.
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",end=' ')
if 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
방법 3 : 파이썬 package 활용
파이썬에는 이러한 비슷한 고민들을 한사람들이 위와 같은 소수확인하는등의 코드들을 간단하게 한두줄로 사용할수 있게끔 Package로 이미 만들어 놓았습니다. 예를 들어 소수확인은 SymPy 라는 파이썬 패키지에도 포함이 되어있고, 간단하게 설치만 하면 바로 사용할수 있습니다.
설치
pip install sympy
사용
from sympy import isprime
사용은 코드 앞쪽에 모듈을 import하고 바로 함수처럼 사용할수 있습니다. 함수는 isprime() 입니다.
from sympy import isprime
number = 600851475143
i=1
while i <= pow(number,0.5):
if number%i==0:
number2=number/i
print(i,number2,end=' ')
if isprime(i):
print(i,"is prime factor")
elif isprime(number2):
print(number2,"is prime factor")
print("")
i+=1
