×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

//エラトステネスのふるい改良版

#include <stdio.h>

#define MAX 1000

int main()
{
    int i,j;
    //エラトステネスのふるい用配列。
    //true なら素数。
    //偶数は明らかに素数でないので最初から排除。
    //2も素数として排除。
    //(MAX+1)個の配列で3〜(2*MAX+3) までの素数に対応
        
    bool Prime[MAX+1];
    
    for(i=0;i<=MAX;i++){//初期化
        Prime[i] = true;
    }

    
    int k;//添え字
    int prm;//添え字に対応する素数

    //添え字k <-> 素数prm の変換式は
    //(2*k+3) <-> prm

    for(i=0; i<=MAX; i++){//i=0からi=MAXまで
        if(Prime[i] == true){
            prm = 2*i+3;//添え字iに対応する素数
            for(k=i+prm; k<=MAX; k+=prm){
            //エラトステネスの超重要ポイント
            //for(j=prm*3,k=(j-3)/2;k<=MAX;j+=2*prm,k=(j-3)/2)と同じ
            //倍数(j+2*prm)を除いていく。偶数はすっ飛ばしてる事に注意。
                Prime[k] = false;//倍数は素数から除外
            }
        }
    }
    
    //合ってるかどうか表示
    printf("%d ",2);//2は無条件で素数としたため。
    for(i=0;i<=MAX;i++){
        if(Prime[i]){
            printf("%d ",2*i+3);
        }
    }
    return 0;
}