[c言語]素数をプログラミングで求めてみる

[c言語]素数をプログラミングで求めてみる

素数は、1より大きな整数で、1と自分自身以外に約数を持っていない(1と自分自身以外の自然数でも割り切れない)数です。

まずは、下記のように、計算量が大きくなりますが、素直に1と自分自身以外の自然数で割り切れるかどうかを調べる方法が考えられます。
num以下の素数をprintf出力しています。

void printPrimeNums(int num){
	int i, j;
	
	for(i = 2; i <= num; i++){
		for(j = 2; j < i; j++){
			//割り切れたらfor文を抜ける
			if(i % j == 0){
			break;
			}
		}
		//for文が最後までループ処理されていたら、途中で割り切れる数がなかったことになるので素数となる
		if(j == i){
			printf("%d ", i);
		}
	}
	printf("\n");
}

逐次調べていくと計算量が大きくなるので、素数の倍数は素数ではない性質(素数で割り切れるので素数ではなくなる)を利用して、計算量を削減してみます。
予め、素数の倍数を、配列に登録しておきます。素数の倍数を配列のインデックスとして、その要素に-1を代入します。
配列の要素が-1となっていれば、素数かどうかの判定処理がいらなくなるので、計算量が削減できます。

void printPrimeNums_2(int num){
	int i, j;
	int* arr = NULL;
	
	arr = calloc(num + 1, sizeof(int));
	if(arr == NULL){
		return;
	}
	
	for(i = 2; i <= num; i++){
		//素数でないので、次のループ処理を実行
		if(arr[i] == -1){
			continue;
		}else{
			printf("%d ", i);
		}
		//素数の倍数を登録
		for(j = 2 * i; j < num; j += i){
			arr[j] = -1;
		}
	}
	printf("\n");
}

サンプルコード

下記がサンプルコードになります。

$ cat sample.c 
#include <stdio.h>
#include <stdlib.h>

void printPrimeNums(int num){
	int i, j;
	
	for(i = 2; i <= num; i++){
		for(j = 2; j < i; j++){
			if(i % j == 0){
			break;
			}
		}
		if(j == i){
			printf("%d ", i);
		}
	}
	printf("\n");
}

void printPrimeNums_2(int num){
	int i, j;
	int* arr = NULL;
	
	arr = calloc(num + 1, sizeof(int));
	if(arr == NULL){
		return;
	}
	
	for(i = 2; i <= num; i++){
		if(arr[i] == -1){
			continue;
		}else{
			printf("%d ", i);
		}
		for(j = 2 * i; j < num; j += i){
			arr[j] = -1;
		}
	}
	printf("\n");
}


int main(){
	printPrimeNums(23);
	printPrimeNums(0);
	printPrimeNums(1);
	printPrimeNums(2);
	printPrimeNums_2(23);
	printPrimeNums_2(0);
	printPrimeNums_2(1);
	printPrimeNums_2(2);	
	
	return 0;
}

$ gcc -o sample sample.c
$ ./sample 
2 3 5 7 11 13 17 19 23 


2 
2 3 5 7 11 13 17 19 23 


2