エラトステネスのふるいで素数判定

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
winter_cat
記事: 16
登録日時: 12年前
住所: Tokyo

エラトステネスのふるいで素数判定

#1

投稿記事 by winter_cat » 12年前

入力されたn(最大6桁)まで何個素数があるか判定します。ただしデータセットは30までとします。
int型なら6桁など余裕だと思ったのですが中々うまくいきません。また思い切ってlong long int にしてもうまくいきませんでした。何故でしょうか??

コード:

#include <iostream>
using namespace std;
int main(){
    int n,set=0;
    while(cin>>n){
        set++;
        if(set==30) break;
        int *array=new int[n];
        int count=0;
        for(int i=2; i<=n; i++){
            array[i]=1; //1で初期化しすべての数を仮に素数としておく
        }

        for(int i=2; i<=n; i++){
            //iを素数だと決定するとiの倍数は素数でないので0にしておく
            if(array[i]==1)
                for(int j=i; i*j<=n; j++) array[i*j]=0;
        }
        for(int i=2; i<=n; i++)
            if(array[i]==1){
                ++count;
            }
        cout<<count<<endl;
    }
    
    return 0;
}

よろしくお願いしますm(__)m

non
記事: 1097
登録日時: 14年前

Re: エラトステネスのふるいで素数判定

#2

投稿記事 by non » 12年前

うまくいかない ではわかりません。
どううまくいかないのか説明してください。
non

non
記事: 1097
登録日時: 14年前

Re: エラトステネスのふるいで素数判定

#3

投稿記事 by non » 12年前

i*j はいくらになるでしょうか?
non

winter_cat
記事: 16
登録日時: 12年前
住所: Tokyo

Re: エラトステネスのふるいで素数判定

#4

投稿記事 by winter_cat » 12年前

48000あたりでSegment faultになります。
i*jにはiの倍数は素数でないのでその印となる0を代入します。

non
記事: 1097
登録日時: 14年前

Re: エラトステネスのふるいで素数判定

#5

投稿記事 by non » 12年前

48000 × 48000 はいくらになるでしょうと、尋ねたのですが。

まず、コンパイラは何を使ってますか?
long long に変更したプログラムを添付してください。
non

アバター
asd
記事: 319
登録日時: 14年前

Re: エラトステネスのふるいで素数判定

#6

投稿記事 by asd » 12年前

winter_cat さんが書きました:48000あたりでSegment faultになります。
i*jにはiの倍数は素数でないのでその印となる0を代入します。
コンパイル、実行環境が不明なので具体的なアドバイスができませんが、
デバッガを使えばSegmentation faultになるのがどこか、どういう状態で起きるのかが解析できるかと思います。
実際に実行してはいませんが、配列の添え字の指定に問題があると思います。
int[n]の配列でアクセスできるのは0~n-1の範囲ですよね。

nonさんも指摘していますが、long longに変更したプログラムも書きだしてもらわないと、
確実なことは言えませんが・・。
Advanced Supporting Developer
無理やりこじつけ(ぉ

閉鎖

“C言語何でも質問掲示板” へ戻る