Drkcore

12 01 2010 Python euler Tweet

Project Euler Problem 41

1からnまでの連続した数をおのおの一つだけ桁にもつ素数のうち最大のものを探せ

987654321から数を減らしながら素直に見つけていくという安直なコードを書いてサブミット。

import math

def make_primes(n):
    primes = [2]
    nums = range(3,n+1,2)
    while 1:
        prime = nums[0]
        if prime ** 2 > n:
            primes += nums
            return primes
        else:
            primes.append(prime)
            nums = [x for x in nums if x%prime != 0]
    return list(set(primes))

def permute(item):
    if len(item) == 1: yield item
    for i in range(len(item)):
        for x in  permute(item[:i]+item[i+1:]):
            yield item[i] + x

def is_prime(n):
    for j in primes:
        if j*j > n: return True
        if n%j == 0: return False
    return True

if __name__ == "__main__":
    num = 7654321
    primes = make_primes(int(math.sqrt(num)))

    for i in permute(str(num)):
        x = int(i)
        if x%2 != 0:
            if is_prime(x):
                print x
                break

それよりもみずぴー日記のコメントが参考になった。

「各桁の数を足した和が3の倍数ならその数自身も3の倍数」って性質から、素数のPanditital数はあるとすれば1桁か4桁か7桁に絞られるんじゃないでしょうか。

えーなんでなんでー????

3の倍数のANo3をみてなるほどなーと感心した。

About

  • もう5年目(wishlistありマス♡)
  • 最近はPythonとDeepLearning
  • 日本酒自粛中
  • ドラムンベースからミニマルまで
  • ポケモンGOゆるめ

Tag

Python Deep Learning javascript chemoinformatics Emacs sake and more...

Ad

© kzfm 2003-2021