前回実装したエラトステネスのふるいを約数の関係を使って高速化する。
例えば次の数の約数は
\begin{align}
12=1,2,3,4,6,12
\end{align}
となる。ここである約数\(n\)の掛け算の組を\(m_{1},m_{2}\)としてあらわすと
\begin{align}
(m_{1},m_{2})=(1,12),(2,6),(3,4)
\end{align}
となる。ここで整数から離れ実数の範囲で考えれば\(m_{1}\)と\(m_{2}\)がともに最大となるような数は明らかに\(\sqrt{n}\)である。
よって、素数の探索で余りを列挙する場合も同様に\(\sqrt{n}\)以下を調べるといい。
tic
N=1000;
n=1:1:N;
plist(1,1)=2;
for i=3:1:N
temp=[];
for j=1:1:length(plist)
if int8(sqrt(i)+1) >= plist(1,j)
temp1=rem(i,plist(1,j));
temp2=horzcat(temp,temp1);
temp=temp2;
clear temp1 temp2
else
break;
end
end
clear sqrti
if all(temp)
temp2=horzcat(plist,i);
clear plist
plist=temp2;
clear temp2
end
clear temp
end
toc
※プログラムではトラブル防止の観点から\(\sqrt{n}+1\)以下を探索している
コメント