セクシー素数

プライムナンバーズ ―魅惑的で楽しい素数の事典 (O’Reilly math series)

プライムナンバーズ ―魅惑的で楽しい素数の事典 (O’Reilly math series)

先日買ったこの本(ブックオフで1400円)をパラパラと見てて引っかかってしまったこの名前。

セクシー素数(sexy primes) (p252)

素数の組み合わせにはいろいろな名前が付いています。例えば、友愛数、双子素数なんてのもあります。単なる数字ですけど、名前がつくとかわいらしくも感じるところが面白いですね。

セクシー素数とは、nとn+6がともに素数(nは正の整数)

ラテン語で6を「sex」というらしく、そこからこの組み合わせがこう呼ばれるようになったみたいです。具体例をあげると、

(5,11),(11,17),(13,19),(17,23),(23,29),(31,37),...

と、続いていきます。

とくに、2つの組み合わせに限らず、3つ組(n,n+6,n+6+6)や4つ組という組み合わせもセクシー素数と言います。ちなみに、6つ組の素数は存在しないということです。

実際に見つけるには

素数なので、まずは素数判定のプログラムがいる。それについては素数判定プログラムで紹介として。あとは簡単で

for i in range(2,10000): #2〜10000まで検証
     if prime.prime2(i)==prime.prime2(i+6)==1: print (i,i+6)

こうすれば、セクシー素数がタプルで返ってくる。

素数判定プログラム

あると便利なプログラム。ここでは少しだけ素数の性質を利用したアルゴリズムを説明する。

素数とは

素数とは、1とその数自身でしか割り切れない数。例えば、2は素数。なぜなら、1と2でしか割れないからである。でも、1は素数ではない。

シンプルな素数判定

素数の定義から、

  • 0と1は非素数である。
  • 2〜n-1までの数にnを割り切る数がなければ、nは素数

ということがわかる。これをそのままプログラムにすれば、素数は判定できる。

def prime(n):
	i=2
	if n==1 or n==0: return 0
	while i<n:	#2〜n-1まで
		if n%i==0:
			return 0
		i+=1
	return 1

この関数primeにnを与えれば、素数なら1、非素数なら0を返す。

メモ

当初、rangeを使って繰り返しをしていたが、数値が大きいときにエラーを起こした。whileにすると解消された。

もう少し、効率的に

上のプログラムは単純労働の力技。すなわち、しらみつぶしというやつで、全部の可能性を検証して素数だと初めてわかるプログラムである。ある1つの数についての検証ならともかく、素数のようにランダムに存在する数を探すならば大変である。

割る範囲は2〜√nまででよい

例えば、n=i*jという式で表されたとすると、iかjは必ず√n以下になる。なぜなら、i=j=√nのときにnになるから。
すなわちnが素数でなければ、√n以下の数にnの約数が存在しているということになる。

素数は奇数である

2以外の素数は必ず奇数である。なぜなら、偶数なら2で割れるから。なので、偶数を検証する必要はない。

変更後プログラム
import math
def prime2(n):
	i=3
	if n==1 or n==0: return 0
	if n%2==0: return 0 #偶数なら非素数
	while i<math.sqrt(n):	#3〜√nまで
		if n%i==0:
			return 0
		i+=1
	return 1

これだけでも、だいぶ早くなる。