파이썬_실전 프로젝트

프로젝트 오일러 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. 600851475143  이수의 약수를 다 찾는 방법은, 숫자크기만큼 루프를 돌면서, 이 수보다 작은 모든수에 대해서, 나누어 봐서 약수인지, 약수이면 다시 소수인지 확인하는 과정으로 하겠습니다.

2. 다른방법으로는 수학공식인, 소인수분해 공식으로 풀어도 됩니다만, 여기서는 따로 설명하지 않겠습니다.

3. 소수는 확인하고자 하는 숫자 크기만큼의 루프를 매번 돌면서, 약수가 있는지를 체크해야하기 때문에, 숫자가 커질수록 당연히 속도는 느려집니다. 그 문제는 아래 코드를 보면서 해결하도록 하죠.

 

- 풀이 -

루프 만들기 테스트
for i in range(1,50): 
    print(i,end=',')
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,

range에는 50 이 안들어 갑니다. 사소한 습관이긴 하나,  종종 error를 만들거나 코드를 복잡하게 하는 원인이 되기도 하는데, 이때는 while문을 사요하는것도 좋습니다. (ex. while i <=50: )

 

약수 확인 테스트
number = 50
for i in range(1,number+1):
    if number%i==0:  #나눠서 0이면 약수 
        print(i)
1
2
5
10
25
50
 
소수확인 테스트
number = 8462696833
for i in range(2,number):      
    if number%i == 0:   #나누어떨어지면
        print(i,"is factor")
        print("not",end=' ') #소수가 아님
        break
    else:
        continue    # else:continue는 여기서는 생략해도 됩니다.
print("prime number") 
839 is factor
not prime number

소수확인을 위해서는, 그숫자만큼의 루프를 매번 돌면서, 나누어 보는게 가장 직관적인 방법입니다.(다른 방법이 있는지는 모르겠네요. 한번 찾아봐야겠습니다.)

 

1. 약수중에 소수인것
number = 1000
for i in range(1,number+1):
    if number%i==0:
        print(i,end=' ')
        if i==1:
            print("not",end=' ')
        for j in range(2,i):
            if i%j == 0:
                print("not",end=' ')
                break
            else:
                continue
        print("prime number")
1 not prime number
2 prime number
4 not prime number
5 prime number
8 not prime number
10 not prime number
20 not prime number
25 not prime number
40 not prime number
50 not prime number
100 not prime number
125 not prime number
200 not prime number
250 not prime number
500 not prime number
1000 not prime number

 

2. 소수확인부분만 함수로 분리
def isPrime(parameter):
    if parameter==1:
        return False
    for j in range(2,parameter):
        if parameter%j == 0:
            return False
        else:
            continue
    return True

number = 1000
for i in range(1,number+1):
    if number%i==0:
        print(i,isPrime(i))
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

 

3. 가장큰 소인수
def isPrime(param):
    if param==1:
        return False
    for j in range(2,param):
        if param%j == 0:
            return False
        else:
            continue
    return True

number = 823856
for i in range(1,number+1):
    if number%i==0 and isPrime(i):
        print(i,"is prime factor")

 

4. 정답계산
def isPrime(param):
    if param==1:
        return False
    for j in range(2,param):
        if param%j == 0:
            return False
        else:
            continue
    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")

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

 

5. 개선

 약수를 찾는 부분에서는, 약수는 제곱근을 중심으로 항상 짝으로 존재하기 때문에, 제곱근 앞부분의 약수를 찾으면, 제곱근 뒤에 있는 약수는 앞에서 찾은 약수로 원래숫자를 나누어서 찾은 다음에, 소수확인 함수를 호출하도록 변경하겠습니다.

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

제곱근을 취할때 round를 취해준것은 range 를 생성할때 정수를 사용해야해서이고, loop에 +1을 해준것도 역시 range 특성때문입니다. 사소한 습관이긴 하나, 이럴때는 while문을 사용하는게 좀더 직관적인것 같습니다.

def isPrime(param):
    if param==1:
        return False
    loop=round(param**0.5)  #소수확인할 수를 제곱근으로 축소.
    for j in range(2,loop+1): #완전제곱수일때를 대비, loop+1을 해주어야함.
        if param%j == 0:
            return False
    return True

number = 600851475143
loopSize = round(number**0.5) # 메인루프크기를 제곱근으로 축소.
for i in range(1,loopSize+1):
    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("")
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

while문을 사용하면, round와 loop+1을 안해주어도 됩니다.

def isPrime(param):
    if param==1:
        return False
    loop=pow(param,0.5)
    j=2
    while j<=loop:
        if param%j ==0:
            return False
        j+=1
    return True

number = 600851475143
loopSize = round(number**0.5)
for i in range(1,loopSize+1):
    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("")

 

다른풀이(소인수 분해 공식)

project-euler 포럼에서 가져온 코드입니다. 계산자체는 간단한데, 수학적인 배경을 좀알아야 하는군요. 코딩에 충분히 숙달되시면 사용해보시기 바랍니다. 일단 지금은 코딩을 익히는게 목적이니깐요.

factor, max_prime = 2, 0
number = 600851475143
while 1:
    if (number%factor == 0):
		number = number/factor
		if factor>max_prime:
			max_prime = factor
		if number == 1:
			break
	else:
		factor+=1
print(max_prime)

 


 

댓글

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