素数の一覧生成

素数、つまり1より大きく、約数が1と自分自身だけの整数を一覧にします。1から100まで、あるいは1兆未満の最後の100万個の数といった範囲のすべての素数、または最初のN個の素数を求められます。個数、見つかった最小と最大の素数、その合計、コピーしてすぐ使えるカンマ区切りの一覧が得られます。

使い方

1. 範囲、または「最初のN個の素数」を選びます。
2. 範囲の場合は、開始と終了を入力します。両端を含みます。
3. 最初のN個の素数の場合は、Nを入力します。
4. 結果欄から一覧をコピーするか、表で10個ずつの行として確認します。

計算式

Sieve of Eratosthenes: for each prime p ≤ √(end), cross out p², p² + p, p² + 2p, … — every number left is prime.

合成数nはどれも√n以下の約数をもつため、終了値の平方根までの素数があれば十分です。開始値が大きい範囲では、区間ふるいを使います。求めた数についてだけ、その小さな素数でふるうので、大きな開始値より下のすべての整数を確保せずに済みます。基礎となる素数の準備には、それでも作業が必要です。最初のN個の素数では、N(ln N + ln ln N)までふるいます。この値はN ≥ 6でN番目の素数を上回ることが証明されています。

計算例

1から100までには素数が25個あります：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。最小は2、最大は97で、合計は1,060です。