素数を数える

Python, 30分プログラム |

30分プログラム、その762。

またもいいネタがないので、素数を数えました。エラトステネスのふるいを使うのも芸がないので、フェルマーテストにしました。

使い方

$ python prime.py
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

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-

from random import uniform

def gcd(n, m):
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

def maybePrime(n):
    a = int(uniform(2,n-1))
    if gcd(n, a) != 1:
        return False
    else:
        return a**(n-1) % n == 1

for n in xrange(2,100):
    if maybePrime(n) and maybePrime(n) and maybePrime(n):
        print n

参考

• 過去の30分プログラム
• フェルマーの小定理 - Wikipedia

ツイートする