はじめに
Pythonで「素数日」を求めたら処理が長すぎて日が暮れそうになったの記事から引き続き、Pythonの練習。
前回は8桁表示が素数になる「素数日」をPythonで求めました(コメント/いいねくださった方ありがとうございます)
2019年5月23日は素数日(20190523:素数)ですが、この素数には面白い性質があります。
- 20190523 :素数
- __190523 :素数
- ___90523 :素数
- _____523 :素数
- ______23:素数
- _______3:素数
このように左から順に数字を取り除いていったときにそのすべての数が素数になります。
※取り除いた結果最上位桁が0の場合はスキップする
このような数を切り捨て可能素数と言います。
すいません嘘です。上記Wikipediaには、
それ自身が素数であるとともに、左から数字を順に取り除いたものが全て素数であり、さらにどの桁も 0 ではないものをいう。
と定義されているので、切り捨て可能素数の亜種ということになります。
今回は「素数日」のうち、切り捨て可能素数(0を含んでもOK)な**「切り捨て可能素数日」をPythonで求めてみます。**
準備
8桁の数を左から切り取って素数判定していくのは多分とてもしんどいので、1桁の素数の左に数を付け加えていって
素数判定を繰り返す方針で行きます。
付け加えられる数の候補は各桁で制限されるので、計算量削減のためこれも考慮に入れます。
- 1桁目(日)：
[3, 7](2,5は素数だが、2桁以上のときそれぞれ2の倍数と5の倍数になる 0の場合も2桁以上で2の倍数) - 2桁目(日)：
[0, 1, 2](1桁目に0と1がこないので、3は取り得ない) - 3桁目(月)：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] - 4桁目(月)：
-
[1](2桁目が0のとき 10月のみ) -
[0,1](2桁目が1か2のとき 1月/2月/11月/12月) -
[0](それ以外)
-
- 5～8桁目(年)：
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
これらの桁に対する入力制限のリストを生成する関数を定義しておきます。
digit_num = {}
def DigitNum(i,j):
if i == 1:
digit_num[i] = [0, 1, 2]
elif i == 3:
if j == 1 or j == 2:
digit_num[i] = [0,1]
else:
digit_num[i] = [0]
else:
digit_num[i] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
iが桁数、jが一桁前の数になります。
1桁目は簡単なのでコード中にそのまま書きます。
4桁目(i=3)で3桁目が0のときの処理が抜けてますが、どうしてもこの関数に組み込む方法が思いつかなかったので、
コード中の条件分岐で別途生成します。
次に、素数の判定をする関数を作ります。
前回記事のコメントで素数判定アルゴリズムや内包表記を教えていただきました。
が、まだ使いこなせるほど理解できていないので、とりあえず思いつくままに書いてみたものになります。
def PrimeCheck(num):
for i in range(3, int(math.sqrt(num))+1, 2): #平方根まで調べれば良いと教えていただきました そらそうだわ
if num % i == 0:
return 0
break
else:
if i == int(math.sqrt(num)) or i == int(math.sqrt(num))-1:
return 1
else:
continue
実装したコード
import math
prime = {}
for i in range(1, 8): #切り取り可能素数日を各桁ごとに格納する
prime[i] = []
digit_num = {}
prime[0] = [3, 7] #1桁目候補
def DigitNum(i,j):
if i == 1:
digit_num[i] = [0, 1, 2]
elif i == 3:
if j == 1 or j == 2:
digit_num[i] = [0,1]
else:
digit_num[i] = [0]
else:
digit_num[i] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
def PrimeCheck(num):
for i in range(3, int(math.sqrt(num))+1, 2):
if num % i == 0:
return 0
break
else:
if i == int(math.sqrt(num)) or i == int(math.sqrt(num))-1:
return 1
else:
continue
for i in range(1,8):
for j in prime[i-1]:
if i == 3 and len(str(j)) <= 2: #4桁目候補の数を生成
digit_num[i] = [1]
else:
DigitNum(i,int(str(j)[0]))
for k in digit_num[i]:
if k == 0: #付け加えた数が0のときの処理
prime[i].append(j)
else:
date = k*(10**i) + j
if PrimeCheck(date) == 1:
prime[i].append(date)
else:
continue
prime[7].sort()
zerofill_prime = []
for i in prime[7]:
zerofill_prime.append(str(i).zfill(8))
print('西暦0年～9999年のうち切り取り可能素数日は' + str(len(zerofill_prime)) + '日')
print(zerofill_prime)
上記コードを実行すると、今回は1秒ほどで結果が帰ってきました。
西暦0年～9999年のうち切り取り可能素数日は832日
['00000103', '00000107', '00000113', '00000223', '00000307', '00000313', '00000317', '00000503', '00000523', '00000607', '00000613', '00000617', '00000823', '00000907', '00001013', '00001103', '00001223', '00010103', '00010223', '00010313']
['00010607', '00010613', '00020107', '00020113', '00021013', '00030103', '00030113', '00030223', '00030307', '00030313', '00031013', '00031223', '00040823', '00050503', '00060103', '00060107', '00060223', '00060317', '00060607', '00060617']
['00061223', '00070223', '00070313', '00070607', '00070823', '00080107', '00080317', '00081013', '00081223', '00090107', '00090313', '00090523', '00090617', '00090823', '00090907', '00100103', '00100313', '00100523', '00100613', '00100823']
['00100907', '00121013', '00130223', '00130307', '00150503', '00180317', '00190313', '00190523', '00190823', '00231223', '00260317', '00261223', '00270223', '00290107', '00290617', '00300317', '00300823', '00301013', '00310223', '00310313']
['00320107', '00320113', '00330103', '00330313', '00331013', '00350503', '00360223', '00360317', '00361223', '00381223', '00390107', '00400307', '00400313', '00400523', '00400607', '00400823', '00450503', '00480107', '00480317', '00490313']
['00500107', '00500113', '00500317', '00501013', '00501103', '00501223', '00510613', '00540823', '00560107', '00560317', '00560617', '00600307', '00600317', '00600823', '00621013', '00630307', '00631013', '00631223', '00660103', '00660607']
['00660617', '00670223', '00670823', '00680107', '00700103', '00700223', '00700307', '00700523', '00700907', '00721013', '00760103', '00760607', '00790523', '00800113', '00801103', '00810223', '00840823', '00860107', '00860317', '00870223']
['00870823', '00890107', '00900103', '00900307', '00900607', '00901013', '00910103', '00920107', '00921013', '00930113', '00931013', '00970313', '00980107', '00990313', '00990523', '01000313', '01000907', '01020113', '01030307', '01050503']
['01060223', '01260317', '01261223', '01320107', '01320113', '01330103', '01330313', '01360223', '01500113', '01501223', '01540823', '01660103', '01870223', '01890107', '01900607', '01921013', '01990523', '02000107', '02000113', '02000503']
['02010103', '02031223', '02070823', '02100313', '02100523', '02130307', '02190523', '02190823', '02300317', '02310223', '02600317', '02670223', '02721013', '02930113', '02970313', '03000103', '03000223', '03000317', '03000523', '03000607']
['03000617', '03001223', '03010313', '03030113', '03040823', '03060107', '03080107', '03081223', '03090313', '03090523', '03100313', '03260317', '03290107', '03300823', '03360223', '03381223', '03400823', '03510613', '03560107', '03600307']
['03660607', '03660617', '03700523', '03760103', '03800113', '03860107', '03860317', '03900307', '03901013', '03970313', '04000523', '04000823', '04000907', '04021013', '04050503', '04081013', '04090907', '04260317', '04261223', '04270223']
['04290107', '04300823', '04330103', '04350503', '04500317', '04501223', '04800113', '04900307', '04990313', '05000113', '05000503', '05010613', '05060317', '05060617', '05070223', '05070823', '05310313', '05400523', '05400823', '05450503']
['05490313', '05631013', '05670823', '05700307', '05721013', '05760103', '06000103', '06000307', '06000317', '06000503', '06000823', '06001013', '06030103', '06030113', '06030313', '06050503', '06070223', '06070313', '06081013', '06090523']
['06090823', '06100613', '06100823', '06100907', '06150503', '06190313', '06190823', '06231223', '06290617', '06300823', '06320113', '06360317', '06390107', '06400607', '06450503', '06480107', '06490313', '06500113', '06500317', '06510613']
['06600823', '06631223', '06660103', '06790523', '06800113', '06860317', '06910103', '06930113', '06931013', '07000313', '07000523', '07020107', '07020113', '07030313', '07060223', '07080107', '07080317', '07500113', '07501103', '07540823']
['07560107', '07660607', '07800113', '07810223', '07840823', '07860107', '07870823', '07900103', '07921013', '08010313', '08060317', '08061223', '08090107', '08121013', '08150503', '08190823', '08300317', '08400823', '08480107', '08760607']
['08910103', '09000223', '09000317', '09000907', '09010103', '09020107', '09020113', '09030313', '09060223', '09060607', '09060617', '09061223', '09070223', '09080107', '09081223', '09100103', '09100313', '09100523', '09100613', '09330103']
['09331013', '09360317', '09400823', '09500107', '09500317', '09501013', '09660617', '09670223', '09670823', '09700307', '09700907', '09721013', '09800113', '09980107', '10000103', '10000223', '10020107', '10030103', '10030313', '10080107']
['10081013', '10081223', '10090313', '10090523', '10090823', '10260317', '10290617', '10320113', '10350503', '10381223', '10500107', '10501013', '10560317', '10560617', '10810223', '10870823', '10900103', '12310223', '12670223', '13081223']
['13360223', '13800113', '15310313', '15400523', '15490313', '15631013', '15760103', '16000307', '16320113', '16660103', '16860317', '18010313', '18061223', '19080107', '20000107', '20000503', '20010223', '20010313', '20031223', '20060107']
['20070823', '20100907', '20130223', '20190523', '20190823', '20300317', '20360317', '20400307', '20400823', '20480107', '20600317', '20660617', '20700103', '20700223', '20700307', '20700523', '20721013', '20910103', '20930113', '21000313']
['21000907', '21050503', '21320107', '21330313', '21360223', '21870223', '21890107', '21990523', '23000617', '23010313', '23100313', '23970313', '24021013', '24050503', '24090907', '24270223', '24350503', '24501223', '24900307', '26001013']
['26070313', '26150503', '26190313', '26931013', '27020113', '27080107', '29331013', '30000307', '30000317', '30010103', '30030307', '30031223', '30061223', '30070823', '30080107', '30080317', '30090107', '30090617', '30301013', '30360223']
['30400523', '30450503', '30500317', '30501223', '30560617', '30630307', '30660103', '30670823', '30680107', '30800113', '30810223', '30870223', '30890107', '30900607', '30921013', '30990313', '30990523', '31000313', '31060223', '31500113']
['31540823', '31921013', '32000113', '32190523', '32970313', '33000103', '33000223', '33060107', '33100313', '33290107', '33300823', '33381223', '33400823', '33510613', '33660607', '33901013', '34000907', '34081013', '34090907', '34330103']
['34501223', '34990313', '35060317', '35070823', '36000317', '36000823', '36100613', '36100907', '36190313', '36450503', '36480107', '36510613', '36631223', '37860107', '37870823', '38480107', '38910103', '39000223', '39060607', '39070223']
['39660617', '39670823', '40000223', '40000313', '40000523', '40030103', '40030313', '40080107', '40080317', '40320113', '40330313', '40500107', '40540823', '40800113', '40920107', '42000107', '42000503', '42070823', '42190523', '42930113']
['42970313', '43000523', '43081223', '43381223', '43510613', '43560107', '43860317', '45700307', '45760103', '46000103', '46000307', '46290617', '46500317', '48121013', '48190823', '48400823', '49000223', '49020113', '49080107', '49501013']
['50000617', '50010313', '50031013', '50060107', '50061223', '50070607', '50100907', '50130307', '50400307', '50400607', '50450503', '50670223', '51260317', '51360223', '51501223', '51890107', '53700523', '53901013', '54021013', '54260317']
['54330103', '54800113', '56390107', '56480107', '57000523', '57030313', '57660607', '57860107', '57900103', '57921013', '59010103', '59670223', '59700307', '60000103', '60000113', '60000313', '60000607', '60001223', '60060103', '60060223']
['60070607', '60081223', '60090313', '60100823', '60100907', '60290617', '60320107', '60350503', '60400313', '60501223', '60600307', '60670223', '60670823', '60680107', '60700223', '60900607', '60920107', '60930113', '61500113', '61660103']
['61870223', '62000503', '62010103', '62190523', '62721013', '63000103', '63081223', '63090523', '63290107', '63360223', '63381223', '63660617', '64000907', '64990313', '65310313', '65670823', '65700307', '66100613', '66100823', '66190823']
['66360317', '66600823', '66631223', '66660103', '66860317', '66931013', '67000523', '67080107', '67870823', '68061223', '68121013', '68150503', '68190823', '68400823', '69070223', '69081223', '69100523', '69500107', '69700907', '69980107']
['70000103', '70000613', '70000823', '70030313', '70050503', '70080317', '70090313', '70090523', '70270223', '70290107', '70300823', '70330313', '70540823', '70621013', '70660103', '70680107', '70800113', '70860107', '70990313', '72000503']
['72190523', '72600317', '72721013', '73000607', '73860317', '75000113', '75000503', '75060617', '75070823', '75400823', '75760103', '76030313', '76081013', '76090823', '76500113', '76860317', '78010313', '78060317', '78061223', '78121013']
['78910103', '79000907', '79060607', '79501013', '80000617', '80010607', '80030113', '80040823', '80070223', '80090107', '80090617', '80400823', '80631013', '80700523', '80760103', '80970313', '81330313', '81870223', '83000317', '83010313']
['83030113', '83040823', '84000823', '84050503', '84081013', '84260317', '84261223', '86070223', '86100613', '86100823', '86450503', '87000313', '87020107', '87030313', '87501103', '87810223', '87870823', '87921013', '89061223', '89100313']
['89360317', '89660617', '90000103', '90000107', '90000607', '90001013', '90010103', '90010313', '90020107', '90021013', '90030223', '90050503', '90060107', '90060317', '90070313', '90080317', '90090823', '90100103', '90121013', '90190523']
['90270223', '90400307', '90480107', '90510613', '90540823', '90560317', '90631223', '90660617', '90700223', '90801103', '90920107', '90921013', '91000313', '91060223', '91260317', '91360223', '91921013', '92190523', '92190823', '92310223']
['92930113', '92970313', '93000317', '93290107', '93560107', '93600307', '93660607', '93660617', '93860317', '94000523', '94260317', '94270223', '94300823', '95070223', '95631013', '95700307', '96001013', '96090823', '96150503', '96190313']
['96300823', '96480107', '96910103', '97020107', '97080107', '97860107', '98910103', '99010103', '99081223', '99331013', '99670223', '99700907']
というわけで、次の切り取り可能素数日は2019年8月23日だそうです。
最後に
CPUファンを大切に。