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

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

Pandigital prime

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를 반환하게 됩니다.

소수 판단

3번 문제의 함수를 쓰던지, 아니면, sympy 모듈의 isprime()을 써도 됩니다. (sympy 설치 필요)

 3번 문제의 속도가 향상된 소수확인 코드

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

 또는 sympy 모듈의 isprime() 함수

from sympy import isprime

방법1 : Brute force

 루프를 가장큰 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 수를 직접 만들어서 쓰면 속도가 더 빠릅니다. (24문제 참고)

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 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 len(string)<9:
        return ''.join(sorted(string+str(len(string)+1)))

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

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