LoginSignup
5
0

More than 3 years have passed since last update.

@yukid

Pythonで「切り捨て可能素数日」を求めたら日は暮れなかった

Last updated at Posted at 2019-06-25

はじめに

Pythonで「素数日」を求めたら処理が長すぎて日が暮れそうになったの記事から引き続き、Pythonの練習。
前回は8桁表示が素数になる「素数日」をPythonで求めました(コメント/いいねくださった方ありがとうございます)

2019年5月23日は素数日(20190523:素数)ですが、この素数には面白い性質があります。

  • 20190523 :素数
  • __190523 :素数
  • ___90523 :素数
  • _____523 :素数
  • ______23:素数
  • _______3:素数

このように左から順に数字を取り除いていったときにそのすべての数が素数になります。
※取り除いた結果最上位桁が0の場合はスキップする
このような数を切り捨て可能素数と言います。
すいません嘘です。上記Wikipediaには、

それ自身が素数であるとともに、左から数字を順に取り除いたものが全て素数であり、さらにどの桁も 0 ではないものをいう。

と定義されているので、切り捨て可能素数の亜種ということになります。
今回は「素数日」のうち、切り捨て可能素数(0を含んでもOK)な「切り捨て可能素数日」をPythonで求めてみます。

準備

8桁の数を左から切り取って素数判定していくのは多分とてもしんどいので、1桁の素数の左に数を付け加えていって
素数判定を繰り返す方針で行きます。

primenum.png

付け加えられる数の候補は各桁で制限されるので、計算量削減のためこれも考慮に入れます。

  • 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ファンを大切に。

5
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
0