エラトステネスのふるいを実装する

素数とは１と自身以外に約数を持たない正の整数のことである。この素数には今のところ法則性が見つかっておらず、探すにはエラトステネスのふるい等を用いる必要がある。

エラトステネスのふるいは次のステップで素数の探索を行う。

• ２を素数にする
• ２の倍数をすべて消す
• 消えなかった最小の数を素数にする
• その数の倍数をすべて消す
• あとは繰り返し

今回は次の手順で実装した

• ２を素数にする
• m(m>2)について、その数以下の素数で割った場合の余りをすべて列挙する
• あまりがすべて０でないなら素数にする
• mが指定された数nになるまで繰り返す

コードはmatlabで実装した。

tic 
N=100;

n=1:1:N;
plist(1,1)=2;

for i=3:1:N
    temp=zeros(1,length(plist));
    for j=1:1:length(plist)
        temp(1,j)=rem(i,plist(1,j));
    end
    if all(temp)
        temp2=horzcat(plist,i);
        clear plist
        plist=temp2;
        clear temp2
    end
    
    clear temp
end

toc

実行後、実行時間がコマンドウインドウに表示され、plistに素数リストが作られる。