素数を判定するプログラムを書いていきます。

単純にC言語で書いたのがコレ。

//$ gcc prime1.c -o prime1

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int isPrime(unsigned long number)
{
int i;
for (i = 2; i < number; i++) {
if (number % i == 0) {
return 0;
}
}
return 1;
}

int main(void)
{
unsigned long number = 9999991;
int answer = 0;
answer = isPrime(number);
if (answer) {
printf("%lu は素数だよ\n", number);
} else {
printf("%lu は素数じゃないよ\n", number);
}
return 0;
}

numberのところに判定する数字を入力してください。

3箇所アルゴリズムを改良して早くしていきます。 

1. まず2や3で割り切れるなら素数ではありません。
 候補ではない数字を最初に除外します。これをエラトステネスの篩といいます。

2. 判定する数字を最後までチェックする必要はありません。
 判定する数字を2つの積で表します。
 たとえば100を2つの積で表してみましょう。
 2 * 50     2で素数かどうかチェック済み
    4 * 25 4で素数かどうかチェック済み
    5 * 20 5で素数かどうかチェック済み
   10 * 10 10で素数かどうかチェック済み

 つまりわざわざ100まで調べなくても良いのです。100のルートを取り10を上限とします。
 素数かどうかを調べるには10以下まで調べれば良いです。
  
3. 素数の数字に注目する。
 5以上100までの素数を書いてみます。
 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
 素数というのは6の倍数の隣の数字になります。確認してください。
 6k ± 1で表せます。

 この3つを考慮してプログラムを書くと次になります。

//$ gcc prime2.c -o prime2

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int isPrime(unsigned long number)
{
unsigned int i;
if (number <= 3 && number > 1) {
return 1;
} else if (number % 2 == 0 || number % 3 == 0) {
return 0;
} else {
for (i = 5; i * i <= number; i += 6) {
if (number % i == 0 || number % (i + 2) == 0) {
return 0;
}
}
}
return 1;
}

int main(void)
{
unsigned long number = 9999991;
int answer = 0;
answer = isPrime(number);
if (answer) {
printf("%lu は素数だよ\n", number);
} else {
printf("%lu は素数じゃないよ\n", number);
}
return 0;
}


これでだいぶ早くなったはずです。
for分がややこしいかもしれませんが、一度紙に書いてトレースして確認してみてください。
 
次回はGMPライブラリーを使って素数判定プログラムに改良していきます。

素数判定プログラム C言語 GMPライブラリー