素数日を計算するスクリプト。ミラーラビン素数判定法（確率的）を決定的バージョンに直しているコードとその結果。参考にした元のページが消えていたのだけれど。

miller_rabin.py

''' partly from http://en.literateprograms.org/Miller-Rabin_primality_test_(Python) '''
def miller_rabin_pass(a, s, d, n):
    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in range(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1
 
def miller_rabin(n):
    '''if n < 1,373,653, it is enough to test a = 2 and 3;
    if n < 9,080,191, it is enough to test a = 31 and 73;
    if n < 4,759,123,141, it is enough to test a = 2, 7, and 61;
    if n < 2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11;'''
    if n < 2: return False
    if n in {2, 7, 61}: return True
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1
    for a in {2,7,61}:
        if not miller_rabin_pass(a, s, d, n):
            return False
    return True

def getlist(year):
    import calendar
    return [int(str(year)+str(m).zfill(2)+str(i+1).zfill(2)) for m in range(1,13) for i in range(calendar.monthrange(year, m)[1])]

if __name__ == '__main__':
    import sys
    year = 2014
    if len(sys.argv)>=2:
        year = int(sys.argv[1])
    for i in getlist(year):
        if miller_rabin(i) is True:
            print(i)

result.txt

20140201
20140213
20140301
20140303
20140327
20140331
20140411
20140423
20140429
20140609
20140613
20140619
20140807
20140823
20140829
20140831
20140907
20140909
20140927
20141003
20141021
20141101
20141111
20141201
20141203
20141207
20141221