Project Euler

「Sympyを使いたい」という目的で.

Problem 5 「最小の倍数」

lcm(range(1, 11))

2520

lcm(range(1, 21))

232792560

関連:
一日一Python:最大公約数を求める(ユークリッドの互除法)
 
 
 
Problem 565 「約数の合計の割り算」

divisors(4)

[1,2,4]

sum(divisors(4))

7

for x in range(1, 21):
    if sum(divisors(x)) % 7 == 0:
        print(x)

4
12
13
20

sum(x for x in range(1, 21) if sum(divisors(x)) % 7 == 0)

49

sum(x for x in range(1, 1000001) if sum(divisors(x)) % 2017 == 0)

150850429

sum(x for x in range(1, 10**11+1) if sum(divisors(x)) % 2017 == 0)

あまりにも遅いので打ち切った.
104で0.4秒
10
5で約4秒
10**6で40秒……という感じ.



10*11なら400万秒か……(´・ω・`)

divisors()よりもfactorint()の方が1.5倍位速いけど,どっちにしろ遅い.
 
 
 
Problem 50 「連続する素数の和」

「divisors」と違って,素数に関する「sieve」クラスのメソッド各種はかなり速い.

%timeit sieve.extend(1000000)

275 µs ± 37.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

「sieve.primerange()」で任意の範囲の素数を求める事ができる.

res = 0
for x in sieve.primerange(2, 1000):
    res += x
    print(f'prime: {x:>4}, sum: {res:>6}, isprime: {isprime(res)}')

prime: 2, sum: 2, isprime: True
prime: 3, sum: 5, isprime: True
prime: 5, sum: 10, isprime: False
prime: 7, sum: 17, isprime: True
prime: 11, sum: 28, isprime: False
prime: 13, sum: 41, isprime: True
prime: 17, sum: 58, isprime: False
prime: 19, sum: 77, isprime: False
prime: 23, sum: 100, isprime: False
prime: 29, sum: 129, isprime: False
prime: 31, sum: 160, isprime: False
prime: 37, sum: 197, isprime: True
prime: 41, sum: 238, isprime: False
prime: 43, sum: 281, isprime: True
prime: 47, sum: 328, isprime: False
prime: 53, sum: 381, isprime: False
prime: 59, sum: 440, isprime: False
prime: 61, sum: 501, isprime: False
prime: 67, sum: 568, isprime: False
prime: 71, sum: 639, isprime: False
prime: 73, sum: 712, isprime: False
prime: 79, sum: 791, isprime: False
prime: 83, sum: 874, isprime: False
prime: 89, sum: 963, isprime: False
prime: 97, sum: 1060, isprime: False
prime: 101, sum: 1161, isprime: False
prime: 103, sum: 1264, isprime: False
prime: 107, sum: 1371, isprime: False
prime: 109, sum: 1480, isprime: False
prime: 113, sum: 1593, isprime: False
prime: 127, sum: 1720, isprime: False
prime: 131, sum: 1851, isprime: False
prime: 137, sum: 1988, isprime: False
prime: 139, sum: 2127, isprime: False
prime: 149, sum: 2276, isprime: False
prime: 151, sum: 2427, isprime: False
prime: 157, sum: 2584, isprime: False
prime: 163, sum: 2747, isprime: False
prime: 167, sum: 2914, isprime: False
prime: 173, sum: 3087, isprime: False
prime: 179, sum: 3266, isprime: False
prime: 181, sum: 3447, isprime: False
prime: 191, sum: 3638, isprime: False
prime: 193, sum: 3831, isprime: False
prime: 197, sum: 4028, isprime: False
prime: 199, sum: 4227, isprime: False
prime: 211, sum: 4438, isprime: False
prime: 223, sum: 4661, isprime: False
prime: 227, sum: 4888, isprime: False
prime: 229, sum: 5117, isprime: False
prime: 233, sum: 5350, isprime: False
prime: 239, sum: 5589, isprime: False
prime: 241, sum: 5830, isprime: False
prime: 251, sum: 6081, isprime: False
prime: 257, sum: 6338, isprime: False
prime: 263, sum: 6601, isprime: False
prime: 269, sum: 6870, isprime: False
prime: 271, sum: 7141, isprime: False
prime: 277, sum: 7418, isprime: False
prime: 281, sum: 7699, isprime: True
prime: 283, sum: 7982, isprime: False
prime: 293, sum: 8275, isprime: False
prime: 307, sum: 8582, isprime: False
prime: 311, sum: 8893, isprime: True
prime: 313, sum: 9206, isprime: False
prime: 317, sum: 9523, isprime: False
prime: 331, sum: 9854, isprime: False
prime: 337, sum: 10191, isprime: False
prime: 347, sum: 10538, isprime: False
prime: 349, sum: 10887, isprime: False
prime: 353, sum: 11240, isprime: False
prime: 359, sum: 11599, isprime: False
prime: 367, sum: 11966, isprime: False
prime: 373, sum: 12339, isprime: False
prime: 379, sum: 12718, isprime: False
prime: 383, sum: 13101, isprime: False
prime: 389, sum: 13490, isprime: False
prime: 397, sum: 13887, isprime: False
prime: 401, sum: 14288, isprime: False
prime: 409, sum: 14697, isprime: False
prime: 419, sum: 15116, isprime: False
prime: 421, sum: 15537, isprime: False
prime: 431, sum: 15968, isprime: False
prime: 433, sum: 16401, isprime: False
prime: 439, sum: 16840, isprime: False
prime: 443, sum: 17283, isprime: False
prime: 449, sum: 17732, isprime: False
prime: 457, sum: 18189, isprime: False
prime: 461, sum: 18650, isprime: False
prime: 463, sum: 19113, isprime: False
prime: 467, sum: 19580, isprime: False
prime: 479, sum: 20059, isprime: False
prime: 487, sum: 20546, isprime: False
prime: 491, sum: 21037, isprime: False
prime: 499, sum: 21536, isprime: False
prime: 503, sum: 22039, isprime: True
prime: 509, sum: 22548, isprime: False
prime: 521, sum: 23069, isprime: False
prime: 523, sum: 23592, isprime: False
prime: 541, sum: 24133, isprime: True
prime: 547, sum: 24680, isprime: False
prime: 557, sum: 25237, isprime: True
prime: 563, sum: 25800, isprime: False
prime: 569, sum: 26369, isprime: False
prime: 571, sum: 26940, isprime: False
prime: 577, sum: 27517, isprime: False
prime: 587, sum: 28104, isprime: False
prime: 593, sum: 28697, isprime: True
prime: 599, sum: 29296, isprime: False
prime: 601, sum: 29897, isprime: False
prime: 607, sum: 30504, isprime: False
prime: 613, sum: 31117, isprime: False
prime: 617, sum: 31734, isprime: False
prime: 619, sum: 32353, isprime: True
prime: 631, sum: 32984, isprime: False
prime: 641, sum: 33625, isprime: False
prime: 643, sum: 34268, isprime: False
prime: 647, sum: 34915, isprime: False
prime: 653, sum: 35568, isprime: False
prime: 659, sum: 36227, isprime: False
prime: 661, sum: 36888, isprime: False
prime: 673, sum: 37561, isprime: True
prime: 677, sum: 38238, isprime: False
prime: 683, sum: 38921, isprime: True
prime: 691, sum: 39612, isprime: False
prime: 701, sum: 40313, isprime: False
prime: 709, sum: 41022, isprime: False
prime: 719, sum: 41741, isprime: False
prime: 727, sum: 42468, isprime: False
prime: 733, sum: 43201, isprime: True
prime: 739, sum: 43940, isprime: False
prime: 743, sum: 44683, isprime: True
prime: 751, sum: 45434, isprime: False
prime: 757, sum: 46191, isprime: False
prime: 761, sum: 46952, isprime: False
prime: 769, sum: 47721, isprime: False
prime: 773, sum: 48494, isprime: False
prime: 787, sum: 49281, isprime: False
prime: 797, sum: 50078, isprime: False
prime: 809, sum: 50887, isprime: False
prime: 811, sum: 51698, isprime: False
prime: 821, sum: 52519, isprime: False
prime: 823, sum: 53342, isprime: False
prime: 827, sum: 54169, isprime: False
prime: 829, sum: 54998, isprime: False
prime: 839, sum: 55837, isprime: True
prime: 853, sum: 56690, isprime: False
prime: 857, sum: 57547, isprime: False
prime: 859, sum: 58406, isprime: False
prime: 863, sum: 59269, isprime: False
prime: 877, sum: 60146, isprime: False
prime: 881, sum: 61027, isprime: True
prime: 883, sum: 61910, isprime: False
prime: 887, sum: 62797, isprime: False
prime: 907, sum: 63704, isprime: False
prime: 911, sum: 64615, isprime: False
prime: 919, sum: 65534, isprime: False
prime: 929, sum: 66463, isprime: True
prime: 937, sum: 67400, isprime: False
prime: 941, sum: 68341, isprime: False
prime: 947, sum: 69288, isprime: False
prime: 953, sum: 70241, isprime: True
prime: 967, sum: 71208, isprime: False
prime: 971, sum: 72179, isprime: False
prime: 977, sum: 73156, isprime: False
prime: 983, sum: 74139, isprime: False
prime: 991, sum: 75130, isprime: False
prime: 997, sum: 76127, isprime: False

100未満は41,1000未満は953(963-10)と分かる.
前からコンボリューションを取ってずらしてみていけば良さそう.

from itertools import accumulate

res = []
for i in range(10):
    for n, x in enumerate(accumulate(sieve.primerange(i+2, i+1000)), 1):
        if x > 100:
            break
        if isprime(x):
            res.append([n, x])
sorted(res, reverse=True)[0]

[6,41]

from itertools import accumulate

res = []
for i in range(10):
    for n, x in enumerate(accumulate(sieve.primerange(i+2, i+1000)), 1):
        if x > 1000:
            break
        if isprime(x):
            res.append([n, x])
sorted(res, reverse=True)[0]

[21,953]

from itertools import accumulate

res = []
for i in range(10):
    for n, x in enumerate(accumulate(sieve.primerange(i+2, i+1000)), 1):
        if x > 10000:
            break
        if isprime(x):
            res.append([n, x])
sorted(res, reverse=True)[0]

[65,9521]

from itertools import accumulate

res = []
for i in range(10):
    for n, x in enumerate(accumulate(sieve.primerange(i+2, i+1000000)), 1):
        if x > 1000000:
            break
        if isprime(x):
            res.append([n, x])
sorted(res, reverse=True)[0]

[543,997651]

広告
カテゴリー: 未分類 パーマリンク

Project Euler への2件のフィードバック

  1. ピンバック: 最大公約数 | 粉末@それは風のように (日記)

  2. ピンバック: 約数 | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中