素数を数える
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