素数

質問

Limit以下の素数をすべて表すプログラムなんですが実行した結果
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿
Input Upper Limit:11
s[0]=3
s[1]=5
s[2]=5
s[3]=5
s[4]=7
s[5]=7
s[6]=7
s[7]=7
s[8]=7
s[9]=9
となるんですが
s[0]=3
s[1]=5
s[2]=7
s[3]=9
にしたいですがどうすればいいのでしょうか？
教えてください。
＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

#include<iostream>
using namespace std;

int main(void)
{
int Limit;
int i,j,n;
int s[256];
n=0;

cout<<"Input Upper Limit:";
cin>>Limit;

for(i=1;i<Limit;i++)
{
for(j=2;j<i;j++)
{
if(i%j==0)
break;
s[n]=i;
cout<<"s["<<n<<"]="<<s[n]<<"\n";
n++;
}
}
return 0;
}

回答No.2

D-Matsu · ベストアンサー

#1でも言われていますがjの初期値が2のため「2で割り切れない」が条件になってしまっています。素数ではなくて奇数を求めてしまってますね。
また、このループ構造ではi <= jかi % j == 0が満たされるまで延々ループを回り続けながら同じ数を配列に格納し続けます。同じ数字が重複表示されるのはこちらが原因です。

素数の条件は「自身より小さいいずれの素数でも割り切れない」ことです。
プログラム的に書きやすい「自身の半分までのあらゆる数で割り切れない」でもいいですが、こういった条件を意識してループと素数判定の部分を作り直してみましょう。

補足

おかげさまでできました。ありがとうございます。

回答No.4

D-Matsu

> 結果Limit:11
> s[0]=2
> s[1]=3
> s[2]=5
> s[3]=7

Limit「以下」ならできてませんよ。Limit「未満」ならこれでいいですが。

回答No.3

chie65536

＞s[0]=3
＞s[1]=5
＞s[2]=7
＞s[3]=9
＞にしたいですがどうすればいいのでしょうか？

素数なら、９が出ちゃダメだろ。２も無いし。

補足

#include<iostream>
using namespace std;

int main(void)
{
int Limit;
int i,j,n;
int s[256];
n=0;

cout<<"Input Upper Limit:";
cin>>Limit;

for(i=1;i<Limit;i++)
{
for(j=2;j<i;j++)
{
if(i%j==0) break;

}
if(i==j)
{
s[n]=i;
cout<<"s["<<n<<"]="<<s[n]<<"\n";
n++;
}
}
return 0;
}

書き直しました

結果Limit:11
s[0]=2
s[1]=3
s[2]=5
s[3]=7
になりました。
ありがとうございました

回答No.1

asuncion

＞if(i%j==0)
＞break;
＞s[n]=i;

１回割り切れなかっただけで素数テーブルに格納しているところがまずいです。
なお、最小の素数は２であることをお忘れなく。

補足

ご意見ありがとうございました。