エラトステネスのふるいで素数を求めるではリストで素数を求めましたが、愚直に奇数ひとつずつを比較して素数を求めてみます。
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の愚直ソースの方が断然早いですね。
コメント