素数の出力

質問

もう一つ問題があります。
0<i<=Xのiについて素数であるものを出力する。というもので条件は

１、Xを指定し、１からXまでの数値を記憶する配列をポインタを用いて確保し、順に１からXまでの値を配列に代入する。

２、配列の各値について、それが素数かを調べる。

３、もし、２で調べた値が素数でない場合は、配列の値を-1に置き換える。

４、配列の全ての値について２、３を繰り返す。

５、すべて調べ終えたら、配列の中身を添字０から順に表示してゆく。
その際、値が -1の場合にはなにも表示しない。

です。
まったく分かりません。教えてください。
素数を調べるー＞割算のあまりをみる。
順に調べるー＞forをつかう。
-1に置き換え
ぐらいしかわかりません。
ちなみに割算でのあまりの検証の仕方も分からないです。

教えてください。

回答No.6

tatsumi01

No. 5 のものですが補足します。エラストテネスの篩ですが、効率を無視すれば簡単です。

(0) 配列 Ａ［１：Ｘ］を取り、Ａ［ｉ］＝：ｉ（ｉ＜＝Ｘ）
(1) 以下 (2)-(3) をｎ＝２からＸまで繰り返す
(2) 次の (3) をｋ＝２ｎからＸまで、ｎとびに繰り返す
(3) Ａ［ｋ］：＝－１

No. 3 で述べたアルゴリズム（エラストテネスの篩）は、上のアルゴリズムを「ｎ＝素数」のときのみ行うものです。しかし、ムダを承知なら素数の判定は不要です。

実際、紙に１～１００くらいまで数字を書いて、ある数の倍数を消して行く処理をやってみて御覧なさい。

回答No.5

tatsumi01

ある数Ｎが素数かどうかを調べるのは、√Ｎより小さい素数でＮを割ってみて、全て素数で割り切れなければ、Ｎは素数です。これを素直にプログラムすれば良いのですが、別の方法を教えます。「エラストテネスの篩」と言います。

まず、２から始めます。２は素数だとわかっています。配列の２番目はそのままにして、２の次から２個おきに４，６，８，・・・と（Ｘまで）－１を埋めてしまいます。

次に、２の次で－１でない要素を探します。この場合は３です。配列の３番目はそのままにして、３の次から３個おきに６，９，１２，・・・と（Ｘまで）－１を埋めます。既に－１が入っていても構いません。

同じように、３の次で－１でない要素を探すと５です。配列の５番目はそのままにして、５の次から５個おきに１０，１５，２０，・・・と（Ｘまで）－１を埋めます。

以下同じようにして、Ｘまでやります。そうすると、配列の中で素数の要素だけに値が残り、素数でないところには－１が入ります。

人によるので一概には言えませんが、√Ｎより小さい素数でＮを割る方法より簡単だと感ずる人もいるでしょう。ある数Ｎの次からＮ個おきに－１を埋めて行くだけですから。

回答No.4

Oh-Orange

★理学部・数学科の大学生ですね。

●アルゴリズム
・scanf 関数で『X』の値を入力して受け取ります。
・その後、『X』個分の int 型配列を malloc 関数で確保します。→ポインタに確保アドレスをセット。
・配列の添え字[0]から添え字[X - 1]までを for 文を用いて素数かどうか調査する。
・素数でない場合は、添え字の配列内容に -1 をセットする。
・あとは、配列の中身を順に表示していきます。

●サンプル
void main()
{
　int *array;　←記憶する配列のポインタ
　int x;　←Xを指定の変数
　int i;

　printf( "X を入力:" ); scanf( "%d", &x );

　if ( (array = (int *)malloc(sizeof(int) * x)) == NULL ){
　　printf( "メモリ不足。\n" );
　　return;
　}
　for ( i = 0 ; i < x ; i++ ){
　　array[ i ] = (i + 1);　←１からXまでの数値を配列に記憶
　}
　for ( i = 0 ; i < x ; i++ ){
　　if ( IsSosu(array,x,i) ){　←素数を判定する関数(自作しましょう)
　　　// 素数の処理
　　}
　　else{
　　　array[ i ] = -1;　←素数ではないので -1 に置き換える
　　}
　}
　for ( i = 0 ; i < x ; i++ ){
　　if ( array[i] != -1 ){
　　　printf( "%d ", array[i] );
　　}
　}
}

●最後に
・『素数を判定する関数』は自分で作ってみて下さい。→ここがポイントですよ。
・上記のサンプルでは IsSosu() 関数が素数のとき TRUE を返して、素数以外なら
　FALSE を返す動作になります。
・BOOL IsSosu( int array[], int x, int n ); が関数のプロトタイプ宣言です。
・int array[] は素数を格納している配列です。
・int x は array 配列の大きさです。
・int n は 調査する素数の配列の添え字数です。
・これを参考に頑張ってみましょう。

回答No.3

PED02744

ほかの方もおっしゃっていますが、「落ち着きましょう」
これは、素数を求めるのを簡単に済ませる方法です。

（１）素数の定義はなんですか？
（２）では、素数でない数値とはなんですか？

「素数とは何か」がわかれば、この１～４は何をさせたいのかがわかります。
でも、設問がおかしいんじゃないかな。これだと1も素数にされちゃいますね(笑)

回答No.2

yeslets

＞素数を調べるー＞割算のあまりをみる。

ここがおかしいような・・・・

３の条件「素数でない場合は－１にする」
ですから、あまりを調べるのではなくて、
「なんかの数で割り切れる」（＝素数でない場合）
かを調べるのですね。

がんばってください。

回答No.1

GootoSchol

とりあえず落ち着くために素数を数えてください。

ゴゴゴゴゴゴゴ・・・

参考URL：

http://www.geocities.jp/hiro00312/box/28_math_sosuu2.html