素数の計算

素数のリストと素数かどうかを判断する関数を作成しよう。

素数を小さい順番に170個含んだ配列:p_lstを作成しよう。

cnt = 170
i = 1
p_lst=[]
while cnt:
i += 1
for j in range(2, i):
if i % j == 0:
break
else:
cnt -= 1
p_lst.append(i)
print(p_lst)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013]

170個目の素数が1000を超えるという感覚です。今後、ある数が素数であるかどうか判断することが増えますが、毎回、1から順に割り算をして素数判定をするのは大変です。そこで、適当な値まで素数をリストにしておき、関数を使って判断することができると便利です。

p_lstを使い引数numが素数の場合はTrue、素数でなければFalseを返す関数を作成しよう。ただし、(1)で求めた最大値より大きな値を渡したときは、sympyモジュールを使って計算するようにしよう。

import sympy
def is_prime(num):
if num <= p_lst[-1]:
if num in p_lst:
return True
else:
return False
else:
return sympy.isprime(num)

sympyモジュールを使うときはimportする必要があります。これを関数の中に入れてしまうと、関数を呼び出すたびにimport文が実行されてしまうので、先に1度だけ実行する方が望ましいといえます。

(2)で作成した関数につき、整数7,8, 170番目の素数、170番目以降の素数および合成数を適用して、関数が正しく動作するか確認しよう。

print(is_prime(7))
print(is_prime(8))
print(is_prime(1013))
print(is_prime(1019))
print(is_prime(1020))

True
False
True
True
False

関数を作成したら、正しく動作することを確認する必要があります。is_prime関数は170番目の素数で処理の方法が分かれるので、170番目より前の素数、合成数、170番目の素数、170番目以降の素数、合成数について確認すれば問題ないと思われます。

(2)で作成した関数を、sympyモジュールを使わない方法で作成し、(3)と同じように動作を確認しよう。

def is_prime(num):
if num <= p_lst[-1]:
if num in p:
return True
else:
return False
else:
for i in range(2, int(num**0.5)):
if num % i == 0:
return False
else:
return True
print(is_prime(7))
print(is_prime(8))
print(is_prime(1013))
print(is_prime(1019))
print(is_prime(1020))

次の数字についてリストを作成し、それぞれの要素の計算結果と、それが素数であるかをsympyモジュールで調べ表示しよう。

$2357$

$2^2+3^3+5^5+7^7$

$2\times3\times5\times7+2+3+5+7$

$2\times3\times5\times7-2-3-5-7$

$2357223335555577777772357$

$2^{19}+3^{19}+5^{19}+7^{19}$

$2^{1013}+3^{1013}+5^{1013}+7^{1013}$

$2 + 3^5 \times 7^{11}$

import sympy
list_2357=[2357,
2**2+3**3+5**5+7**7,
2*3*5*7+2+3+5+7,
2*3*5*7-2-3-5-7,
2357223335555577777772357,
2**19+3**19+5**19+7**19,
2**1013+3**1013+5**1013+7**1013,
2+3**5*7**11 ]
for i in list_2357:
print(i,is_prime(i))

2357 True
826699 True
227 True
193 True
2357223335555577777772357 True
11417969834487023 True
12142679563228033424635341670005387510823412249852134553474965420429186337733573950522113279632132533861827280437430273269452841029915940398173430412321321085489633512687219288143610261218489996039589428685869622852801173657959784273834714066408856009458567186582587325446256603155157471952311243489562164280714349812921891321858677333205354879079027357515517844976212766082207387474992425395868846130364246979645060726350430465126385461696155047537229542426357158320846603344465341562987135138610891126245991431477426380062780893931087056776473643637678927187194372174626426472224017990881502642572436483902735018467866599684044008428245215483614547905517739626198223802503709714696026580405533518870236672247108045228930825545850834514681094370554152545188333278444281671003087522215484006467822438930422198808765437830035897632431549609514820603243396047 True
480490398551 True

小さい順番に4つの素数、2,3,5,7に対し、いろいろな演算をするとその結果が素数になります。多少こじつけ的なものもありますが、素数に対する神秘を予感してもらえると嬉しいです。最後の問題は、すさまじい数字になりますが、sympyモジュールを使うとこんな数字でも簡単に素数かどうかを判断してくれます。

次の計算結果とその値が素数であるか調べよう。ただし、$p_n$は小さい順にn番目の素数であることをいいます。

$2^{p_7} + 3^{p_5} + 5^{p_3} + 7^{p_2}$

x=is_prime(2**p_lst[7-1]+3**p_lst[5-1]+5**p_lst[3-1]+7**p_lst[2-1])
print(x)

True

788からはじまる連続する6つの整数を、素数の小さい順番$p_1$～$p_6$で割った時の余りを計算しよう。

for i in range(6):
print((788+i)%p_lst[i],end='')
print()

8757193191の左からn桁を順次取り出して、$p_n$で順次割った時の余りを計算しよう。

num='8757193191'
for i in range(len(num)):
print(int(num[:i+1]),p_lst[i],int(num[:i+1])%p_lst[i])

8 2 0
87 3 0
875 5 0
8757 7 0
87571 11 0
875719 13 0
8757193 17 0
87571931 19 0
875719319 23 0
8757193191 29 0

左から桁を1つずつ切り捨てていっても素数になるものを左切り捨て可能素数（left-truncatable prime）といいます。次の整数について、左切り捨て可能素数であるか確認しよう。

95918918997653319693967

96686312646216567629137

357686312646216567629137

import sympy
def left_truncatable(num):
while num>10:
num=int(str(num)[1:])
print(num,sympy.isprime(num))
left_truncatable(95918918997653319693967)
left_truncatable(96686312646216567629137)
left_truncatable(357686312646216567629137)

5918918997653319693967 True
918918997653319693967 True
18918997653319693967 True
8918997653319693967 True
918997653319693967 True
18997653319693967 True
8997653319693967 True
997653319693967 True
97653319693967 True
7653319693967 True
653319693967 True
53319693967 True
3319693967 True
319693967 True
19693967 True
9693967 True
693967 True
93967 True
3967 True
967 True
67 True
7 True
6686312646216567629137 True
686312646216567629137 True
86312646216567629137 True
6312646216567629137 True
312646216567629137 True
12646216567629137 True
2646216567629137 True
646216567629137 True
46216567629137 True
6216567629137 True
216567629137 True
16567629137 True
6567629137 True
567629137 True
67629137 True
7629137 True
629137 True
29137 True
9137 True
137 True
37 True
7 True
57686312646216567629137 True
7686312646216567629137 True
686312646216567629137 True
86312646216567629137 True
6312646216567629137 True
312646216567629137 True
12646216567629137 True
2646216567629137 True
646216567629137 True
46216567629137 True
6216567629137 True
216567629137 True
16567629137 True
6567629137 True
567629137 True
67629137 True
7629137 True
629137 True
29137 True
9137 True
137 True
37 True
7 True

105から210までにあるすべての素数pに対して、210から差し引いた値が素数かどうか確認しよう。

num=list(sympy.primerange(105,210))
for i in num:
print(i,210-i,sympy.isprime(210-i))

107 103 True
109 101 True
113 97 True
127 83 True
131 79 True
137 73 True
139 71 True
149 61 True
151 59 True
157 53 True
163 47 True
167 43 True
173 37 True
179 31 True
181 29 True
191 19 True
193 17 True
197 13 True
199 11 True