C言語：素数をチェックする関数（高速版）

素数を普通にチェックすると10万以上の数くらいになってしまうと異常に遅くなるので、大きな数でも高速に素数のチェックができる関数です。

一応関数内にコメントが書いてありますが、よく分からないと思いますので下の参考URLの解説を読んでみてください。

isPrimeNumber.c

1#include <math.h>
2 
3int isPrimeNumber(int n){
4    int i;
5 
6    if(n < 2) return 0;          /* 2未満は素数ではない */
7    else if(n == 2) return 1;   /* 偶数の2のみ素数である */
8    else if(n % 2 == 0){            /* 2以上の偶数は素数ではない */
9        return 0;
10    }
11    else{   /* 奇数の場合 */
12        for(i=3; i<=sqrt(n); i+=2){      /* 3～ルートnまでの奇数のみチェック(高速化のため) */
13            if(n % i == 0) return 0;    /* 割り切れた場合は素数ではない */
14        }
15        return 1;   /* どれも割り切れなかったときは素数である */
16    }   
17}

使い方
参考URL

使い方

isPrimeNumberSample.c

1#include <stdio.h>
2#include <math.h>
3 
4int isPrimeNumber(int n){
5    int i;
6 
7    if(n < 2) return 0;          /* 2未満は素数ではない */
8    else if(n == 2) return 1;   /* 偶数の2のみ素数である */
9    else if(n % 2 == 0){            /* 2以上の偶数は素数ではない */
10        return 0;
11    }
12    else{   /* 奇数の場合 */
13        for(i=3; i<=sqrt(n); i+=2){      /* 3～ルートnまでの奇数のみチェック(高速化のため) */
14            if(n % i == 0) return 0;    /* 割り切れた場合は素数ではない */
15        }
16        return 1;   /* どれも割り切れなかったときは素数である */
17    }   
18}
19 
20int main(void){
21    int i;
22 
23    /* 1~100000までの素数を表示 */
24    for(i=0; i<=100000; i++){
25        if(isPrimeNumber(i)){
26            printf("%d ", i);
27        }
28    }
29    printf("\n");
30 
31    return 0;
32}