본문 바로가기
컴퓨터

[오일러프로젝트]01~15 풀이

by Oh 선생 2019. 10. 7.

#0. 오일러프로젝트라는게 있다. 

https://projecteuler.net/about

 

About - Project Euler

About Project Euler What is Project Euler? Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficie

projecteuler.net

홈페이지에서 코딩으로 풀만한 문제를 제공하고, 그걸 풀어서 답을 제출하는 곳인데,

파이썬 연습 겸 애들 방과후 소재 찾기 겸 해서 겸사겸사 풀기 시작해봤다. 

그런데 어째 3번부터 풀기가 빡세다...--; 일단은 3번까지의 풀이 모음. 

* 10.16. 수정: 10번까지의 풀이를 추가했다. 

* 10.18. 수정: 15번까지의 풀이를 추가했다. 

 

#1. 1000 이하의 3과 5의 배수를 모두 찾아 더하기. 

''' 
Euler Project 1: 
Find the sum of all the multiples of 3 or 5 below 1000. 
''' 
multiples=[] 
for i in range(0, 1000): 
    if i%3==0: 
        multiples.append(i) 
    else: 
        if i%5==0: 
            multiples.append(i) 
            if i%3==0: 
                multiples.remove(i) 

 

처음 내가 짰던 건 이런 식. 0부터 1000가지 3의 배수와 5의 배수를 리스트에 몽창 넣고, 그 다음에 15의 배수를

다시 빼내는 식으로 짰는데... 알고보면 이게 더 쉽다. 

''' 
Euler Project 1: 
Find the sum of all the multiples of 3 or 5 below 1000. 
''' 

multiples=[] 

for i in range(0,1000): 
    if i%3==0 or i%5==0:  #if 명령어에 or을 줄 수 있는걸 알면 이게 훨 쉽다.  
        multiples.append(i) 
         
print(sum(multiples))

 

if 에 or을 넣을 수 있다는걸 알면 쉽게 해결했을 문제. 답은 포스팅하지 않는다(어차피 돌리면 나올거라...). 

 

#2. 피보나치수열 중, 400만을 넘지 않는 짝수의 합을 구하기. 

a=0
b=1
f=0
fibo=[]
evenfibo=[]
while f<4000000:
    f=a+b
    a=b
    b=f
    fibo.append(f)

for j in fibo:
    if j%2 ==0:
        evenfibo.append(j)

print(evenfibo)
print(sum(evenfibo))

 

f로 피보나치수열을 생성하고, 그 중에 짝수만을 모아서, 합을 구하는 식으로 만들었다. 

 

#3. 600851475143의 가장 큰 소인수를 구하는 문제. 

이거땜에 시간을 많이 끌었다. 최초의 구상은 저 수보다 작은 소수를 다 확인한 다음에, 

그 소수가 저 수의 인수인지를 확인해서, 가장 큰 수를 뽑아내는 방식으로 접근했다. 

import math
n=int(input('Input an integer that want to find prime factor: '))
prime=[]
factor=[]

def check_prime(number):
    if number !=1:
        for factor in range(2,number):
            if number%factor==0:
                return False
    else:
        return False
    return True

for i in range(1,n):
    if check_prime(i):
        prime.append(i)


for i in prime:
    if n%i ==0:
        factor.append(i)
print(factor)

 

첫 번째 for 구문에서 입력받은 n보다 작은 소수를 몽땅 찾고, 

두 번째 for 구문에서 그 소수 중 n의 약수가 되는 애들을 찾으려는 작전이었는데...

막상 실행해보면 한 5자리 수까지는 무난히 결과가 나오는데, 문제의 600851475143는 결과가 안나온다

 

한 6자리부터 실행시간이 눈에 띄게 느려지는 걸 봐선 더 빠르게 풀 수 있는 알고리즘이 필요한 듯 했다. 

그래서 인수분해를 더 빠르게 하는 알고리즘을 찾아보니 페르마 알고리즘이 나오더라.

 

* 페르마 알고리즘

대충 요령은 N=a^2-b^2 으로 표현된다면, N=(a-b)(a+b)로 표현되므로, a=(N의 제곱근의 정수부분 + 1)로 잡아서

c=a^2-N을 계산하고, 이때 c가 어떤 수의 제곱이 될 때까지 계속 a를 증가시켜간다. 그러다가 c가 어떤 수의 

제곱이 되면, 그 c가 b^2인거고, 그때의 a+b와 a-b가 N을 나누는 두 수인 거다. 

이때 a+b, a-b가 소수인지는 아직 모르지만, 비교적 빠르게 N의 덩어리를 나눌 수 있다는 장점이 있다. 

예를 들어 N=20이면 (N의 제곱근의 정수+1)=4+1=5. 그래서 a=5.

c=25-20 = 5이므로 실패. 이제 a를 1 키워서 6을 만든다. 

c=36-20=16=4^2이므로, b=4. 따라서 20=(6+4)(6-4)=10*2로 쪼갤 수 있다. 

참고는 여기 https://en.wikipedia.org/wiki/Fermat%27s_factorization_method

 

Fermat's factorization method - Wikipedia

From Wikipedia, the free encyclopedia Jump to navigation Jump to search Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: N = a 2 − b 2 . {\displaystyle N=a^{2}-b

en.wikipedia.org

import math

n=int(input('Input number:'))

#입력된 수를 두 수의 곱으로 바꿔주는 함수 using 페르마 알고리즘

primefactor=[]

def factor(n):
    if math.sqrt(n).is_integer()==False:
        a=int(math.sqrt(n))+1
        b2=a**2 - n
        t=math.sqrt(b2).is_integer()
        while t==False:
            a=a+1
            b2=a**2 -n
            t=math.sqrt(b2).is_integer()

        return a, int(math.sqrt(b2))
    else:
        return int(math.sqrt(n)), 0

    
p, q = factor(n)
print(p+q,p-q)

 

이걸 구현한 코드는 위와 같다(그런데 몇몇 수들은 작동이 안된다. 18 같은거.)

이걸 이용해서 어떻게든 한 번에 결과가 나오게끔 만들어보려고 했으나... 실패. 그래서 결국 수를 쪼갰다. 

600851475143를 저기에 넣으면 1234169와 486847이 나오고, 이걸 다시 돌리면 정답을 찾을 수 있다. 

이걸 원하는 만큼 돌리는 로직이 잘 떠오르지 않아서... 답을 찾긴 했으나 예쁘지 않다. 

그래서 인터넷을 뒤지니 다음과 같은 답이 나온다. 

def lpf(x):
    lpf=2
    while (x>lpf):
        if (x%lpf==0):
            x=x/lpf

        else:
            lpf+=1
    return x
print(lpf(600851475143))

# https://stackoverflow.com/questions/12999706/stuck-on-project-euler-3-in-python

 

가장 큰 소인수를 일단 2로 잡고, x가 그거보다 클 동안에는 계속 소인수를 키워가면서 x를 나누는거다.

x를 계속 막 나누다보면 결국 남는게 가장 큰 소인수라는 흐름인데,

덩어리가 큰 x를 처음부터 빠르게 쪼개나간다는 점에서 좋아보인다. 내가 접근하는 방식은 모든 소인수를 찾고, 

그 다음에 최대의 소인수를 찾는 방법이었는데 문제에서 요구한건 그냥 최대의 소인수를 찾는거니까 굳이

그렇게 할 필요는 없다는 게 포인트.  

여튼 여기에서 페르마 알고리즘을 새로 배웠고, 애들은 왜 N의 제곱근을 기준으로 삼는지를 생각해보게끔

할 수 있겠다. 

 

#4. 회문(回文, palindrome) 이라는게 있다. 토마토, 기러기 처럼 앞으로 읽으나 뒤로 읽으나 똑같은 것. 

4번 문제는 세 자리 수의 곱으로 표현되는 최대의 회문을 찾는 것이었다.

대충 구상은 세 자리 수의 곱을 왕창 만든 뒤, 그 중 회문인 것을 모두 찾아 그것의 최댓값을 찾으면 되겠다 싶었다. 

수학문제라기보다는 그냥 코딩 연습에 가까웠다. 

'''
Euler 문제 4번.
세 자리 수의 곱으로 표현되는 최대의 회문 찾기.
'''

import math #없어도 된다. 두 수의 곱으로 표현하고자 함. 

def palindrome(n):
    a=str(n)
    b=a[::-1]
    if a==b :
        return True
    else:
        return False


def factor(n): #여긴 없어도 되는 부분. 두 수의 곱으로 표현하고자 함. 
    if math.sqrt(n).is_integer()==False:
        a=int(math.sqrt(n))+1
        b2=a**2 - n
        t=math.sqrt(b2).is_integer()
        while t==False:
            a=a+1
            b2=a**2 -n
            t=math.sqrt(b2).is_integer()

        return a, int(math.sqrt(b2))
    else:
        return int(math.sqrt(n)), 0
    
p=[]
for i in range(110,1000,11):
    for j in range(100,1000):
        n=i*j
        if palindrome(n)==True:
            p.append(n)

print(max(p))
i, j = factor(max(p)) #없어도 됨. 
print(i+j,i-j) #없어도 됨. 
        

 

 

#5. 5번은 1부터 20까지의 수로 모두 나누어지는 최소의 양수를 찾는 문제. 결국 1~20의 최소공배수를 찾자는 거다. 

나는 n을 입력받아 1~n까지의 수로 모두 나누어지는 최소의 양수를 찾는 문제로 바꿔 풀었다. 

수학적으로 생각해보면 각 수를 모두 소인수분해해서 나온 소인수를 몽땅 곱하고 가장 큰 지수를 택하면 되지만...

내가 그걸 코딩으로 구현하기가 어렵다. 그래서 어떻게 접근했냐면

- 일단 n을 입력받아서, n 이하의 소인수를 모두 찾아 곱한다(1개씩만 곱한단 소리다. 12=2*2*3이니까 2와 3만 곱한다).

- 최소공배수는 당연히 '모든 소인수의 곱'의 배수다. 

- (모든 소인수의 곱)*1을 해서, 이걸 1~n까지의 수로 몽땅 나눠본다. 나눠지는 만큼 카운트를 센다. 카운트가 n이 되면 멈춘다. 

- n까지 나눠봤는데 카운트가 n이 안되면 (모든 소인수의 곱)*2를 해서 이걸 다시 1~n까지의 수로 나누고 카운트를 센다. 카운트가 n이 될 때 까지 반복. 

구현한건 다음과 같다. 

'''
Euler 5.
'''

def prime_checker(number):
    if number !=1:
        for factor in range(2,number):
            if number%factor==0:
                return False
    else:
        return False
    return True

primeunder=[]

def prime_gen(n):
    for i in range(2,n+1):
        if prime_checker(i)==True:
            primeunder.append(i)

def product(arr):
    ans=1
    for i in arr:
        ans = ans*i
    return ans

n=int(input('몇 까지의 최소공배수를 구할까요?:'))
prime_gen(n)
p=product(primeunder)

count=0
k=1

while count<=n:
    for i in range(1,n+1):
        if (k*p)%i == 0 :
            count=count+1
        else:
            k=k+1
            count=0

print(k*p)
            



#6. 제곱의 합과 합의 제곱의 차를 구하는 문젠데, 이건 너무 쉬워서 생략. 

#7. 10001번째 소수를 찾는 문제. 

사실 코드는 간단하다. 소수를 찾아서, 리스트에 넣고, 10001번째를 불러오면 된다. 

'''
Euler 7
'''

import math #나중에 추가
def prime_checker(number):
    if number !=1:
        for factor in range(2,int(math.sqrt(number))+1): #이것도 나중에 수정. 
            if number%factor==0:
                return False
    else:
        return False
    return True

prime=[]
n=2
while len(prime)<10001:
    if prime_checker(n)==True:
        prime.append(n)
        n=n+1
    else:
        n=n+1

a=prime[-1]
print(a)

        

 

처음엔 int(math.sqrt(number))+1) 부분을 그냥 number로 했었는데, 이게 작업이 엄청 오래 걸린다. 

그래서 어떻게 하면 조금 줄일까 싶어서 고민하다가 다음의 명제를 사용했다. 

* 주어진 자연수 N이 소수이기 위한 필요충분조건은 sqrt(N)보다 작은 모든 소수로 나누어지지 않는 것이다. 

증명은 귀류법을 쓰면 간단히 해결되므로 생략. 

(https://math.stackexchange.com/questions/2134091/a-natural-number-n-is-prime-if-and-only-if-for-all-primes-p-le-sqrt-n-p 여길 참조하면 된다.)

나중에 찾아보니 이게 원래 소수인지 판별할 때 많이 쓰는 알고리즘이라더라. 

#8. 8번은 1000자리 수(--;)를 펼쳐놓고, 그 중 연속된 13개의 수를 곱했을 때 가장 크게 뽑을 수 있는 수를 찾는 문젠데 이것도 쉬우니까 생략. 수를 시퀀스 자료형으로 바꾸고, 인덱스로 연속된 13개를 곱하게 만들어 리스트에 넣은 뒤, 최댓값 찾으면 된다. 인덱스 놀음이 조금 까다로울 뿐...

 

#9. 어째 뒤로 갈 수록 쉬워진다. a^2 + b^2 = c^2을 만족하는 자연수 중(즉, 피타고라스 쌍 중) a+b+c=1000을 만족하는 a, b, c에 대하여 abc의 값을 구하라는 문제. 

'''
Euler8
'''
import math

for i in range(1, 1000):
    for j in range(1,1000):
        a=i**2 + j**2
        if math.sqrt(a).is_integer() == True:
            s=i+j+math.sqrt(a)
            if s==1000:
                print(i,j,math.sqrt(a))
                print(i*j*math.sqrt(a))

구상은 a와 b를 1000까지 왕창 돌려가면서 제곱해서 더하고,

그 결과가 정수의 제곱이라면(즉, 두 수의 제곱의 합에 제곱근을 씌운 게 정수인지 테스트하고)

a+b+c가 1000이 되는지를 확인해서 답을 찾는 식으로 했다. 

평소 잘 안쓰던 .is_integer() 메소드를 썼다는 게 조금 인상깊은 점. 

 

#10. 200만 이하의 소수의 합을 구하는 문제. 기본은 7번과 같다. 

'''
Euler 10
'''
import math

def prime_checker(number):
    if number !=1:
        for factor in range(2,int(math.sqrt(number))+1):
            if number%factor==0:
                return False
    else:
        return False
    return True


def prime_gen(n):
    primesum=2
    for i in range(3,n+1,2):
        if prime_checker(i)==True:
            primesum=primesum+i
    return primesum
            
n=int(input('몇 까지의 소수의 합을 구할까요?:'))
p=prime_gen(n)
print(p)

 

별 생각없이 코딩하면 수가 커서 컴퓨터가 답을 못찾는다. sqrt(number)를 통해서 과정을 좀 줄여줘야 한다. 

 

#11. 다음과 같이 주어진 수의 배열에서, 가로, 세로, 대각선의 곱이 가장 큰 4개의 수를 찾기. 

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

이차원 배열을 이용해서 문제를 풀면 간단하게 되겠다 싶었다. 

그런데 주어진 수를 그대로 입력하면 '08', '02' 같은 애들 때문에 처리가 안된다. 

그런 애들을 8, 2, ... 로 바꿔주고 이차원 배열을 만들어서 풀었다. 

(물론 머리를 더 쓰면 수동으로 안해도 되고, 또 그걸 원하는 문제긴 하겠지만... 한 번에 하나만 하자.

나는 여기에선 이차원 배열을 쓰는게 목표였다.)

'''
Euler 11
가로세로대각선 4개 곱한 것 중 최댓값 찾기
'''

a1=[8 ,2 ,22 ,97 ,38 ,15 ,0 ,40 ,0 ,75 ,4 ,5 ,7 ,78 ,52 ,12 ,50 ,77 ,91 ,8]
a2=[49 ,49 ,99 ,40 ,17 ,81 ,18 ,57 ,60 ,87 ,17 ,40 ,98 ,43 ,69 ,48 ,4 ,56 ,62 ,0]
a3=[81 ,49 ,31 ,73 ,55 ,79 ,14 ,29 ,93 ,71 ,40 ,67 ,53 ,88 ,30 ,3 ,49 ,13 ,36 ,65]
a4=[52 ,70 ,95 ,23 ,4 ,60 ,11 ,42 ,69 ,24 ,68 ,56 ,1 ,32 ,56 ,71 ,37 ,2 ,36 ,91]
a5=[22 ,31 ,16 ,71 ,51 ,67 ,63 ,89 ,41 ,92 ,36 ,54 ,22 ,40 ,40 ,28 ,66 ,33 ,13 ,80]
a6=[24 ,47 ,32 ,60 ,99 ,3 ,45 ,2 ,44 ,75 ,33 ,53 ,78 ,36 ,84 ,20 ,35 ,17 ,12 ,50]
a7=[32 ,98 ,81 ,28 ,64 ,23 ,67 ,10 ,26 ,38 ,40 ,67 ,59 ,54 ,70 ,66 ,18 ,38 ,64 ,70]
a8=[67 ,26 ,20 ,68 ,2 ,62 ,12 ,20 ,95 ,63 ,94 ,39 ,63 ,8 ,40 ,91 ,66 ,49 ,94 ,21]
a9=[24 ,55 ,58 ,5 ,66 ,73 ,99 ,26 ,97 ,17 ,78 ,78 ,96 ,83 ,14 ,88 ,34 ,89 ,63 ,72]
a10=[21 ,36 ,23 ,9 ,75 ,0 ,76 ,44 ,20 ,45 ,35 ,14 ,0 ,61 ,33 ,97 ,34 ,31 ,33 ,95]
a11=[78 ,17 ,53 ,28 ,22 ,75 ,31 ,67 ,15 ,94 ,3 ,80 ,4 ,62 ,16 ,14 ,9 ,53 ,56 ,92]
a12=[16 ,39 ,5 ,42 ,96 ,35 ,31 ,47 ,55 ,58 ,88 ,24 ,0 ,17 ,54 ,24 ,36 ,29 ,85 ,57]
a13=[86 ,56 ,0 ,48 ,35 ,71 ,89 ,7 ,5 ,44 ,44 ,37 ,44 ,60 ,21 ,58 ,51 ,54 ,17 ,58]
a14=[19 ,80 ,81 ,68 ,5 ,94 ,47 ,69 ,28 ,73 ,92 ,13 ,86 ,52 ,17 ,77 ,4 ,89 ,55 ,40]
a15=[4 ,52 ,8 ,83 ,97 ,35 ,99 ,16 ,7 ,97 ,57 ,32 ,16 ,26 ,26 ,79 ,33 ,27 ,98 ,66]
a16=[88 ,36 ,68 ,87 ,57 ,62 ,20 ,72 ,3 ,46 ,33 ,67 ,46 ,55 ,12 ,32 ,63 ,93 ,53 ,69]
a17=[4 ,42 ,16 ,73 ,38 ,25 ,39 ,11 ,24 ,94 ,72 ,18 ,8 ,46 ,29 ,32 ,40 ,62 ,76 ,36]
a18=[20 ,69 ,36 ,41 ,72 ,30 ,23 ,88 ,34 ,62 ,99 ,69 ,82 ,67 ,59 ,85 ,74 ,4 ,36 ,16]
a19=[20 ,73 ,35 ,29 ,78 ,31 ,90 ,1 ,74 ,31 ,49 ,71 ,48 ,86 ,81 ,16 ,23 ,57 ,5 ,54]
a20=[1 ,70 ,54 ,71 ,83 ,51 ,54 ,69 ,16 ,92 ,33 ,48 ,61 ,43 ,52 ,1 ,89 ,19 ,67 ,48]


m=[a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12,a13,a14,a15,a16,a17,a18,a19,a20]

vertical=[]
horizontal=[]
rdigonal=[]
ldigonal=[]

for i in range(0, 20):
    for j in range(0,17):
        horizontal.append(m[i][j]*m[i][j+1]*m[i][j+2]*m[i][j+3])

max_hor=max(horizontal)

for i in range(0,17):
    for j in range(0,20):
        vertical.append(m[i][j]*m[i+1][j]*m[i+2][j]*m[i+3][j])

max_ver=max(vertical)

for i in range(0,17):
    for j in range(0,17):
        rdigonal.append(m[i][j]*m[i+1][j+1]*m[i+2][j+2]*m[i+3][j+3])

max_rdig=max(rdigonal)

for i in range(0,17):
    for j in range(3,20):
        ldigonal.append(m[i][j]*m[i+1][j-1]*m[i+2][j-2]*m[i+3][j-3])

max_ldig=max(ldigonal)

maxwhole=max(max_hor, max_ver, max_rdig, max_ldig)

print(maxwhole)
        
    

 

#12. 

12는 500개 이상의 약수를 갖는 최소의 삼각수 찾기. 

n번째 삼각수란 1, 3, 6, 10, 15, 21, 28, 36, 45, 55... 처럼 1부터 n까지 더한 수를 말한다. 

이때 55의 경우 1, 5, 11, 55의 4개의 약수를 가진다. 이런 식으로 500개 이상의 약수를 갖는 삼각수를 찾는 문제다. 

대충 풀이는

- 일단 삼각수를 생성하고

- 삼각수에 대해서 약수의 개수를 구한다. 

로 각을 잡았다. 

그래서 처음에는 

'''
Euler12
500개 이상의 약수를 가지는 최소의 삼각수 찾기
'''

#삼각수 생성하기
def tri_gen(n):
    t=0
    for i in range(1,n+1):
        t=t+i
    return t


#약수의 개수 구하기
def count_factor(n):
    count=2
    for i in range(2, int(n/2)+1):
        if n%i==0:
            count=count+1
    return count

count=0
n=1
while count<100:
    t=tri_gen(n)
    count=count_factor(t)
    n=n+1

print(t)
    

 

이런 식으로 만들었다. 삼각수 t에 대하여, 1부터 t/2까지 다 t를 나눠보면서 그게 약순지 아닌지 확인하는 방식. 

그런데 이렇게 하면 돌아는 가는데 컴퓨터가 답을 못낸다. 더 빠른 방법이 필요하다. 

그래서 생각한게 이거. 

'''
Euler12
500개 이상의 약수를 가지는 최소의 삼각수 찾기
'''

import math

#삼각수 생성하기
def tri_gen(n):
    t=0
    for i in range(1,n+1):
        t=t+i
    return t

#소수 확인하기
def prime_checker(number):
    if number !=1:
        for factor in range(2,int(math.sqrt(number))+1):
            if number%factor==0:
                return False
    else:
        return False
    return True

#약수의 개수 구하기(2)
def count_factor2(n):
    if prime_checker(n)==True:
        num_factors=2
    else:
        num_factors=1
        for i in range(2, int(math.sqrt(n))+1):
            power=0
            while n%i==0:
                n=n/i
                power=power+1
            num_factors=num_factors*(power+1)
        if n>int(math.sqrt(n)):
            num_factors=num_factors*2
    return num_factors


count=0
n=1
while count<500:
    t=tri_gen(n)
    count=count_factor2(t)
    n=n+1

print(t)



        

 

이번엔 약수의 개수 = (소인수의 지수+1)*(소인수의 지수+1)*... 로 구하는 방법을 썼다. 

주어진 t에 대해서 t를 2로 나누고, 지수를 하나 세고,  t/2를 새로 t로 만든다. 

그리고 다시 2로 나눠지면 또 나누고, 지수를 하나 더하고, t/2를 새로운 t로 다시 만든다(이때의 t는 초기의 t보다 2로 2번 나눠진 값이다). 

이제 2로 안나눠지면 다시 t를 3으로 나누면서 같은 작업 반복, 4로는 당연히 안나눠지니까 스킵, 5로 나누면서 같은 작업 반복...뭐 그런 방식이다. sqrt(n)까지의 소수로 계속 나누면서 n 자체를 작게 만들어가는 방법. 

중간에 10, 14 같은 수에서 오류가 좀 나서 자잘하게 손을 좀 봐줬다. 아무튼 이렇게 하면 답이 나왔다. 

아무튼 소인수분해 해야 하는 문제는 몇 번을 해봐도 까다롭다. 

#13. 

13번은

37107287533902102798797998220837590246510135740250
46376937677490009712648124896970078050417018260538
74324986199524741059474233309513058123726617309629
91942213363574161572522430563301811072406154908250
23067588207539346171171980310421047513778063246676
89261670696623633820136378418383684178734361726757
28112879812849979408065481931592621691275889832738
44274228917432520321923589422876796487670272189318
47451445736001306439091167216856844588711603153276
70386486105843025439939619828917593665686757934951
62176457141856560629502157223196586755079324193331
64906352462741904929101432445813822663347944758178
92575867718337217661963751590579239728245598838407
58203565325359399008402633568948830189458628227828
80181199384826282014278194139940567587151170094390
35398664372827112653829987240784473053190104293586
86515506006295864861532075273371959191420517255829
71693888707715466499115593487603532921714970056938
54370070576826684624621495650076471787294438377604
53282654108756828443191190634694037855217779295145
36123272525000296071075082563815656710885258350721
45876576172410976447339110607218265236877223636045
17423706905851860660448207621209813287860733969412
81142660418086830619328460811191061556940512689692
51934325451728388641918047049293215058642563049483
62467221648435076201727918039944693004732956340691
15732444386908125794514089057706229429197107928209
55037687525678773091862540744969844508330393682126
18336384825330154686196124348767681297534375946515
80386287592878490201521685554828717201219257766954
78182833757993103614740356856449095527097864797581
16726320100436897842553539920931837441497806860984
48403098129077791799088218795327364475675590848030
87086987551392711854517078544161852424320693150332
59959406895756536782107074926966537676326235447210
69793950679652694742597709739166693763042633987085
41052684708299085211399427365734116182760315001271
65378607361501080857009149939512557028198746004375
35829035317434717326932123578154982629742552737307
94953759765105305946966067683156574377167401875275
88902802571733229619176668713819931811048770190271
25267680276078003013678680992525463401061632866526
36270218540497705585629946580636237993140746255962
24074486908231174977792365466257246923322810917141
91430288197103288597806669760892938638285025333403
34413065578016127815921815005561868836468420090470
23053081172816430487623791969842487255036638784583
11487696932154902810424020138335124462181441773470
63783299490636259666498587618221225225512486764533
67720186971698544312419572409913959008952310058822
95548255300263520781532296796249481641953868218774
76085327132285723110424803456124867697064507995236
37774242535411291684276865538926205024910326572967
23701913275725675285653248258265463092207058596522
29798860272258331913126375147341994889534765745501
18495701454879288984856827726077713721403798879715
38298203783031473527721580348144513491373226651381
34829543829199918180278916522431027392251122869539
40957953066405232632538044100059654939159879593635
29746152185502371307642255121183693803580388584903
41698116222072977186158236678424689157993532961922
62467957194401269043877107275048102390895523597457
23189706772547915061505504953922979530901129967519
86188088225875314529584099251203829009407770775672
11306739708304724483816533873502340845647058077308
82959174767140363198008187129011875491310547126581
97623331044818386269515456334926366572897563400500
42846280183517070527831839425882145521227251250327
55121603546981200581762165212827652751691296897789
32238195734329339946437501907836945765883352399886
75506164965184775180738168837861091527357929701337
62177842752192623401942399639168044983993173312731
32924185707147349566916674687634660915035914677504
99518671430235219628894890102423325116913619626622
73267460800591547471830798392868535206946944540724
76841822524674417161514036427982273348055556214818
97142617910342598647204516893989422179826088076852
87783646182799346313767754307809363333018982642090
10848802521674670883215120185883543223812876952786
71329612474782464538636993009049310363619763878039
62184073572399794223406235393808339651327408011116
66627891981488087797941876876144230030984490851411
60661826293682836764744779239180335110989069790714
85786944089552990653640447425576083659976645795096
66024396409905389607120198219976047599490197230297
64913982680032973156037120041377903785566085089252
16730939319872750275468906903707539413042652315011
94809377245048795150954100921645863754710598436791
78639167021187492431995700641917969777599028300699
15368713711936614952811305876380278410754449733078
40789923115535562561142322423255033685442488917353
44889911501440648020369068063960672322193204149535
41503128880339536053299340368006977710650566631954
81234880673210146739058568557934581403627822703280
82616570773948327592232845941706525094512325230608
22918802058777319719839450180888072429661980811197
77158542502016545090413245809786882778948721859617
72107838435069186155435662884062257473692284509516
20849603980134001723930671666823555245252804609722
53503534226472524250874054075591789781264330331690

를 몽땅 더하고 앞자리 10개를 구하는 문제. 

이걸 11번처럼 풀면 기절할 것같고... 이제 여기에서 파일에서 불러오기를 처음으로 썼다. 

일단 위의 수를 입력한 txt파일을 하나 만들고 Euler13.txt로 이름을 붙였다. 

그리고 나서 코드는 다음과 같다. 

'''
Euler 13
'''

with open('Euler13.txt','r') as file:
    lines=file.readlines()

    
a=list(map(int, lines))

sum=sum(a)
str_sum=str(sum)
print(str_sum[0:10:])

 

저렇게 파일을 열면 lines리스트에 위의 수들이 줄줄이 들어간다. 

이렇게 lines에 들어간 애들이 str인지 int인지 잘 모르겠어서 일단 map 명령으로 모두 int로 바꾸어 a라는 리스트를 만든다. 

그리고 나선 a의 합을 구하고, 문자열로 바꿔서 시퀀스형으로 바꿔주고, 슬라이스를 써서 앞의 10개만 읽으면 끝. 

간단하다. 

 

#14. 

14번은 Collatz(콜라츠)수열에 관계된 문제다. 

초깃값에 대해서, 그 수가 짝수면 반으로 나누고, 홀수면 3배를 곱하고 1을 더한다. 같은 작업 반복. 

예를 들어 10->5->16->8->4->2->1 

1이 나오면 이 뒤는 계속 4-2-1 반복이기 때문에 끝난걸로 간주한다. 

(그리고 이때 수열의 길이는 7이라고 생각한다.)

여기에서 콜라츠 추측이 나온다: "어떤 수로 시작하더라도 콜라츠 수열은 1로 끝나는가?"

위키피디아를 보니 아직 이 문제에 대한 증명은 이루어지지 않았으며, 에르되쉬 팔이 이 문제에 500달러의 현상금을

걸었다고도 한다(너무 짠거 아니냐...).

아무튼 오일러 프로젝트 14번 문제는 100만까지의 수로 시작하는 콜라츠 수열 중,

가장 수열의 길이가 긴 수열은 몇으로 시작하는 수열이냐? 라는 거다. 

문제가 복잡한데 비해 풀이는 간단하다. 

'''
Euler 14
'''

#Generating Collatz sequence
def collatz(n):
    seq=[n]
    while n!=1:
        if n%2 ==0:
            n=n/2
            seq.append(n)
        else:
            n=3*n+1
            seq.append(n)
    return seq

max_length = 1
for i in range(1,1000000):
    if max_length < len(collatz(i)):
        max_length=len(collatz(i))
        starting=i

print(starting, max_length)

콜라츠 수열을 만드는 함수를 하나 만들어서, 리스트에 수열을 다 때려넣고, 최대의 길이를 갖는 리스트를 찾는다. 

정답은 평소처럼 비공개. 최대 길이는 525가 나온다. 

 

#15.

15번은 가로세로가 각각 20인 격자로 된 길에서, 왼쪽위 모서리에서 오른쪽아래 모서리로 가는

경우의 수를 묻는 문제다. 

이거야 이미 답이 정해진 문제라 쉽다. 

'''
Euler 15
'''

#Factorial
def factorial(n):
    f=1
    for i in range(1,n+1):
       f=f*i
    return f

a,b= map(int, input('가로, 세로를 각각 얼마로 할까요?:').split())

print(int(factorial(a+b)/(factorial(a)*factorial(b))))

 

팩토리얼을 구해주는 함수를 만들고, 거기에 넣어서 계산하면 끝. 여기에선 값을 입력받도록 만들었다. 


오일러 프로젝트도 15번까지 풀어보니 모든 문제를 풀어볼 필요는 없지 싶다. 

앞으로는 수학적으로 좀 얘기할 만한 거리가 있는 문제만 잘 선별해 풀어서 포스팅해야 겠다. 

막짤은 문센 수업 중인 우리 아들. 

 

댓글0