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

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

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

isPrimeNumber.c

#include <math.h>

int isPrimeNumber(int n){
	int i;

	if(n < 2) return 0;			/* 2未満は素数ではない */
	else if(n == 2) return 1;	/* 偶数の2のみ素数である */
	else if(n % 2 == 0){			/* 2以上の偶数は素数ではない */
		return 0;
	}
	else{	/* 奇数の場合 */
		for(i=3; i<=sqrt(n); i+=2){		/* 3～ルートnまでの奇数のみチェック(高速化のため) */
			if(n % i == 0) return 0;	/* 割り切れた場合は素数ではない */
		}
		return 1;	/* どれも割り切れなかったときは素数である */
	}	
}

使い方
参考URL

使い方

isPrimeNumberSample.c

#include <stdio.h>
#include <math.h>

int isPrimeNumber(int n){
	int i;

	if(n < 2) return 0;			/* 2未満は素数ではない */
	else if(n == 2) return 1;	/* 偶数の2のみ素数である */
	else if(n % 2 == 0){			/* 2以上の偶数は素数ではない */
		return 0;
	}
	else{	/* 奇数の場合 */
		for(i=3; i<=sqrt(n); i+=2){		/* 3～ルートnまでの奇数のみチェック(高速化のため) */
			if(n % i == 0) return 0;	/* 割り切れた場合は素数ではない */
		}
		return 1;	/* どれも割り切れなかったときは素数である */
	}	
}

int main(void){
	int i;

	/* 1~100000までの素数を表示 */
	for(i=0; i<=100000; i++){
		if(isPrimeNumber(i)){
			printf("%d ", i);
		}
	}
	printf("\n");

	return 0;
}