파이썬으로 수학문제 풀기- 프로젝트 오일러(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를 반환하게 됩니다.

 

소수 판단

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)

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

댓글

댓글 본문
  1. nomadlife
    아 감사합니다. 다시보니, 코드에 문제가 좀 있네요. 조만간 수정해놓겠습니다.
    대화보기
    • 바림
      마지막에 최종 코드 그대로 인코딩하면 오류가 나네요 ㅠㅠ 3.7.x

      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)))

      i = '1'

      while i:
      if isprime(int(i)) == True:
      print(i, "is prime & pandigit")
      i = get_next_permutation(i)


      그래서 이거로 수정해서 풀이했습니다!
      올려주신 코드 보면서 덕분에 이 문제 풀었습니다 ㅠㅠ 감사합니다.
    버전 관리
    nomadlife
    현재 버전
    선택 버전
    graphittie 자세히 보기