C言語で愚直に素数を求める

前回はリストで素数を求めましたが、愚直に奇数ひとつずつを比較して素数を求めてみます。

takk@deb83:~$ cat -n prime.c
     1	#include <stdio.h>
     2	
     3	int main(int argc, char* argv[])
     4	{
     5		int i,j;
     6		int maxnum = atoi(argv[1]);
     7	
     8		printf("2");
     9		for(i = 3; i <= maxnum; i += 2){
    10			for(j = i-2; j > 2; j-=2){
    11				if((i % j) == 0)
    12					break;
    13			}
    14			if(j < 2)
    15				printf(" %d",i);
    16		}
    17		puts("\n");
    18	}
takk@deb83:~$ 

実行してみます。

takk@deb83:~$ gcc prime.c
takk@deb83:~$ ./a.out 100 | fold -s40
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
takk@deb83:~$ 

では処理時間の計測をしてみます。引数で指定した上限数に一番近い素数だけを表示するプログラムにします。

takk@deb83:~$ cat -n prime_last.c
     1	#include <stdio.h>
     2	
     3	int main(int argc, char* argv[])
     4	{
     5		int i,j,prime;
     6		int maxnum = atoi(argv[1]);
     7	
     8		for(i = 3; i <= maxnum; i += 2){
     9			for(j = i-2; j > 2; j-=2){
    10				if((i % j) == 0)
    11					break;
    12			}
    13			if(j < 2)
    14				prime = i;
    15		}
    16		printf("%d\n",prime);
    17	}

これを実行すると。。。8.2秒でした。

takk@deb83:~$ time ./a.out 100000
99991

real	0m8.208s
user	0m8.204s
sys	0m0.000s
takk@deb83:~$ 

前回作ったpythonのリストを使ったスクリプトではどうでしょうか。素数を表示する箇所は以下のように最後の番号のみしています。
print prime[-1]

takk@deb83:~/blog/src$ time python prime_last.py 100000
99991

real	0m18.546s
user	0m18.512s
sys	0m0.020s
takk@deb83:~/blog/src$ 

18.5秒でした。このぐらいの数であれば、Cの愚直ソースの方が断然早いですね。

Leave a Reply

Your email address will not be published. Required fields are marked *

CAPTCHA