파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 27번 문제 - 2차 함수로 소수만들기

n^2 + 40n + 41

위 2차 함수에 1~40 까지 대입하면, 40개의 소수가 생성된다고 합니다.

n^2 - 79n + 1601

이런 함수는 1~80 까지 대입하면, 80개의 소수가 생성된다고 합니다.

n^2 + an + b

문제는 위의 식에서 a,b 절대값이 1000 보다 작을때, 앞의 예제처럼 1부터 시작해서 최대갯수의 소수가 생성되도록 하는 a,b의 값을 찾아서 두수의 곱을 계산하는 문제입니다.

 

Quadratic primes

https://projecteuler.net/problem=27

 

먼제 예제를 코드로 만들어 보도록 하죠. 소수확인 함수는 앞선 문제들에서 몇번 사용했기 때문에 그대로 가져오도록 하겠습니다.

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

for n in range(40):
    value=pow(n,2)+n+41
    print(value,end=' ')
    if is_prime(value):
        print("True")
print(0)

#범위내 모든 소수의 갯수 확인
count =0
for i in range(41,1602):
    if is_prime(i):
        count+=1
print(count)
41 True
43 True
47 True
53 True
61 True
71 True
...
...
1447 True
1523 True
1601 True

240

41~1601까지 40여개의 소수가 출력되는걸 볼수 있습니다. 혹시나 해서, 41~1601사이의 모든 소수를 카운트 해봤더니, 240개로, 해당 2차방정식으로 생성되는 소수는 범위내의 모든 소수가 아님을 알수 있습니다.

 

위 식을 조금 수정하면 두번째 예제의 1~80개의 소수도 생성할수 있습니다.

 

아래는 답을 구하는 코드입니다. -1000 에서 1000 까지의 루프문 두개를 중첩시켜서, 모든 a,b 값을 조사하고, 최대값을 골라내도록 했습니다.

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

max_n=0
for a in range(-1000,1001):
    for b in range(-1000,1001):
        n=0
        while True:
            value = n**2 + a*n + b
            if value>0 and is_prime(value):
                n+=1
            else:
                if n>max_n:
                    max_n = n
                    print("a:",a,"b:",b,"new max value n:",n,a*b)
                    break
                else:
                    break
a: -1000 b: 2 new max value n: 1 -2000
a: -996 b: 997 new max value n: 2 -993012
a: -499 b: 997 new max value n: 3 -497503
a: -325 b: 977 new max value n: 4 -317525
a: -245 b: 977 new max value n: 5 -239365
a: -197 b: 983 new max value n: 6 -193651
a: -163 b: 983 new max value n: 7 -160229
a: -131 b: 941 new max value n: 8 -123271
a: -121 b: 947 new max value n: 9 -114587
a: -105 b: 967 new max value n: 11 -101535
a: -61 b: 971 new max value n: 71 -59231

댓글

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