2が現れる素数という面白い素数が紹介されていた。
2が現れる素数 - INTEGERS
昔せっかく高速素数判定器を作ったので、どうせならNが現れる素数を見つけてやろう！と思い立った。
プログラム
（※プログラムはpython(2.7.12)で動作します）
高速素数判定のプログラム（再掲）
primechecker.pyという名前で保存
import random import numpy as np class PrimeChecker: def __init__(self, list_limit = pow(10,3)): if list_limit < 5: list_limit = 5 self.prime_list = self.set_prime_list(list_limit) self.list_limit = list_limit @staticmethod def set_prime_list(n): def mark(primes,x): for i in xrange(2*x, n+1, x): primes[i-2] = False primes = [(i%2!=0 and i%3!=0 and i%5!=0) for i in range(2,n+1)] primes[0] = primes[1] = primes[3] = True for x in xrange(7, int(np.sqrt(n+1))+1): if primes[x-2]: mark(primes, x) prime_list = [] for i in range(n-1): if primes[i]: prime_list.append(i+2) return prime_list def is_prime(self, n): k = 50 # number of iteration times if n < self.list_limit: return True if n in self.prime_list else False for prime in self.prime_list: if n%prime == 0: return False else: s, d = 0, n-1 while d%2==0: s,d = s+1, d/2 while k > 0: k = k-1 a = random.randint(1,n-1) t, y = d, pow(a,d,n) while t != n-1 and y != 1 and y != n-1: y = pow(y,2,n) t <<= 1 if y != n-1 and t%2 == 0: return False return True if __name__=="__main__": pc = PrimeChecker() pc.is_prime(58427) # True
Nが現れる素数を見つけるためのプログラム
from primechecker import PrimeChecker def display_letter(p): """ display letter on commandline for checking """ print("-"*18) for i in range(0,216,18)[::-1]: print(str(p/pow(10,i) + pow(10,18))[1:]) p = p%pow(10,i) print("-"*18) def tex_command(p,num,f): """ output tex command to file """ f.write("\\begin{align} \n") for i in range(0,216,18)[::-1]: f.write("&") string = str(p/pow(10,i) + pow(10,18))[1:] string = string.replace(str(num), "\color{red}{%d}"%num) f.write(string) p = p%pow(10,i) f.write("\\\\ \n") f.write("\\end{align} \n") letters = [""" 000000000000000000 000000001111000000 000000011111000000 000000111111000000 000001101111000000 000000001111000000 000000001111000000 000000001111000000 000000001111000000 000000001111000000 000001111111111000 000000000000000000 """,""" 000000000000000000 000000222222000000 000022222222220000 000222000002220000 000000000022220000 000000000222200000 000000002222000000 000000022220000000 000002222000000000 000222222222222000 000222222222222000 000000000000000000 """,""" 000000000000000000 000000333333000000 000033333333330000 000333000003333000 000000000033333000 000000033333300000 000000033333300000 000000000033333000 000333000003333000 000033333333330000 000000333333000000 000000000000000000 """,""" 000000000000000000 000000004444400000 000000044444400000 000000444444400000 000004440444400000 000044400444400000 000444000444400000 004444444444444400 004444444444444400 000000000444400000 000000000444400000 000000000000000000 """] pc = PrimeChecker() f = open("result.txt","w") for n, letter in enumerate(letters): num = n+1 prime_letter = int(letter.replace("\n","")) for i in range(1000,10000)[::-1]: if (i/1000)!=num and ((i%1000)/100)!=num and ((i%100)/10)!=num and i%10 != num: pl = prime_letter pl += pow(10,215) * (i/1000) pl += pow(10,198) * ((i%1000)/100) pl += pow(10,17) * ((i%100)/10) pl += i%10 if pc.is_prime(pl): display_letter(pl) tex_command(pl,num,f) break f.close()
