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

프로젝트 오일러 41번 - Pandigital prime

n자리 pandigit 이면서 소수인 가장큰수를 찾는문제입니다.

 

Pandigital prime

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

 

pandigital 판단
def is_pandigit(num):
    string=str(num)
    for i in range(1,len(string)+1):
        if not str(i) in string:
            return False
    return True
        
print(is_pandigit("123465"))
True

 길이만큼의 루프를 돌면서, 그만큼의 정수가 다 있는지 검사합니다.

 

줄여서 아래처럼 쓸수도 있습니다.

def is_pandigit(num):
    string=str(num)
    if all(str(i) in string for i in range(1,len(string)+1)):
        return True
    return False

print(is_pandigit("123465"))
True

 all() 은 괄호안의 모든 항이 참(또는 1)일때 참이 됩니다. 하나라도 False면 False를 반환하게 됩니다.

 

 루프를 가장큰 pandigital인 '987654321' 까지 주고, 실행을 시켜보면,,,

number = 1
while number < 987654321:
    if is_pandigit(number):
        if isprime(number):
            print(number,"is pandigit & prime number")
    number+=1

,,결과가 나오긴 하는데, 속도가 좀 느립니다. (제 느린 pc에서는 더 느리더군요)

 

속도개선

위 코드처럼 하면 간단하게 pandigital인지는 검사할수 있지만, loop 크기가 커지면 속도가 느려지는 단점이 있습니다. 산술적으로 10번 검사해서 1번꼴로 나오는 수니깐요. 그래서 이왕이면 규칙을 알기때문에 pandigital 수를 직접 만들어서 쓰면 속도가 더 빠릅니다.

from sympy import isprime

def get_next_permutation(string):
    for i in range(len(string)-1,0,-1):
        if string[i-1] < string[i]:
            target = sorted(string[i-1:])
            new_num = target.pop(target.index(string[i-1])+1)
            last_nums = ''.join(target)
            return string[:i-1] + new_num + last_nums
    if i==1 and len(string)<9:
        return ''.join(sorted(string+str(len(string)+1)))
        

get_next_permutation('123456')
'123465'

 

그리고 메인 루프문을 추가해주면

from sympy import isprime

def get_next_permutation(string):
    for i in range(len(string)-1,0,-1):
        if string[i-1] < string[i]:
            target = sorted(string[i-1:])
            new_num = target.pop(target.index(string[i-1])+1)
            last_nums = ''.join(target)
            return string[:i-1] + new_num + last_nums
    if i==1 and len(string)<9:
        return ''.join(sorted(string+str(len(string)+1)))
    return False

i='1'
while i:
    if isprime(i):
        print(i,"is pandigit & prime number")
    i=getpermutation(i)

처음보다 결과가 빨리 나오는것을 볼수있습니다.

댓글

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