この春から大学でプログラムを学び始めた者です。
講義にて、素数の演算と表示に関する話がありました。
その中で、エラトステネスの篩とアトキンの篩について紹介があり、どちらの方がどのくらい早いのかと、入力した数以下の素数と処理時間を表示するものを組もうとしています。
しかし、エラトステネスの篩は出来たのですが、アトキンの篩が上手いこと組めずにいます。
そこで、ネットから参考となるコードを探したのですが、C言語で記述されたものを見つけることができませんでした。
次に、C++のコードをC言語に出来ないかと試み、エラーは消えたのですが、知識が足りないためギャップを埋めきれなかったようで、前述した素数と処理時間の表示という動作をしませんでした。(素数が表示されず処理時間のみ表示される)
どう違っているのか教えて下さい!
該当のソースコード
C
1#include <stdio.h> 2#include <math.h> 3#include <sys/time.h> 4 5#define M 1000 6#define true 1 7#define false 0 8 9int main(){ 10 struct timeval s, e; 11 gettimeofday(&s, NULL); 12 13 /*process*/ 14 void atkin() { 15 int n,z,y,x,k; 16 double N = 1000; 17 int isprime[200]; 18 for (z = 1; z <= 5; z += 4) { 19 for (y = z; y <= sqrt(N); y += 6) { 20 for (x = 1; x <= sqrt(N) && (n = 4*x*x+y*y) <= M; ++x) 21 isprime[n] = !isprime[n]; 22 for (x = y+1; x <= sqrt(N) && (n = 3*x*x-y*y) <= M; x += 2) 23 isprime[n] = !isprime[n]; 24 } 25 } 26 for (z = 2; z <= 4; z += 2) { 27 for (y = z; y <= sqrt(N); y += 6) { 28 for (x = 1; x <= sqrt(N) && (n = 3*x*x+y*y) <= M; x += 2) 29 isprime[n] = !isprime[n]; 30 for (x = y+1; x <= sqrt(N) && (n = 3*x*x-y*y) <= M; x += 2) 31 isprime[n] = !isprime[n]; 32 } 33 } 34 for (y = 3; y <= sqrt(N); y += 6) { 35 for (z = 1; z <= 2; ++z) { 36 for (x = z; x <= sqrt(N) && (n = 4*x*x+y*y) <= M; x += 3) 37 isprime[n] = !isprime[n]; 38 } 39 } 40 for (n = 5; n <= sqrt(N); ++n) 41 if (isprime[n]) 42 for (k = n*n; k <= M; k+=n*n) 43 isprime[k] = false; 44 isprime[2] = isprime[3] = true; 45} 46 47 gettimeofday(&e, NULL); 48 printf("time = %lf\n", (e.tv_sec - s.tv_sec) + (e.tv_usec - s.tv_usec)*1.0E-6); 49 return 0; 50} 51
参考にしたサイト
時間の計測
アトキンの篩のやり方
アトキンの篩
アトキンの篩
C言語のtrueとfalseについて
C++の記号一覧
補足情報(FW/ツールのバージョンなど)
Oracle VM VirtualBox
Oracle VM VirtualBox Extension Pack
Cent OS 7
C99以前
回答2件
あなたの回答
tips
プレビュー