質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
86.02%
アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

C++ 素数判定 配列のグローバル化

Kinsho
Kinsho

総合スコア17

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

2回答

0グッド

0クリップ

563閲覧

投稿2022/02/19 15:00

編集2022/02/19 15:01

競技プログラミングの問題を解いているときに約200までの素数の配列を作る必要があったのですが、配列の宣言場所を変えただけで不思議なバグが発生しました。

①まず、このようにすると素数だけprime配列の値が1になります。
(エラトステネスの篩を使った方が早いとかは分かってます。)

C++

1#include<bits/stdc++.h> 2using namespace std; 3void _main(); int main() { _main(); } 4 5int prime[210]; 6void _main() { 7for(int i=2;i<=210;i++){ 8 bool p=true; 9 for(int j=2;j<=sqrt(i);j++){ 10 if(i%j==0)p=false; 11 } 12 if(p)prime[i]=1; 13} 14for(int i=0;i<210;i++){if(prime[i]==1)cout<<i<<' ';} 15} 16 17出力 182 3 5 7 11 13 17 19 23 29 31 37 41 1943 47 53 59 61 67 71 73 79 83 89 97 20101 103 107 109 113 127 131 137 139 21149 151 157 163 167 173 179 181 22191 193 197 199

②しかし、int prime[210];の宣言を関数の内部に入れると

C++

1#include<bits/stdc++.h> 2using namespace std; 3void _main(); int main() { _main(); } 4 5void _main() { 6int prime[210]; 7for(int i=2;i<=210;i++){ 8 bool p=true; 9 for(int j=2;j<=sqrt(i);j++){ 10 if(i%j==0)p=false; 11 } 12 if(p)prime[i]=1; 13} 14for(int i=0;i<210;i++){if(prime[i]==1)cout<<i<<' ';} 15} 16 17出力 18 2 3 5 7 11 13 16 17 19 23 29 31 37 19 41 43 47 53 59 61 67 71 73 79 83 20 89 96 97 101 103 107 109 113 127 21 131 137 139 149 151 157 163 167 22 173 179 181 191 193 197 199 204 206

このように16とか96とか204とか206とか素数でない数字がなぜか入ってきます。

これらの数字はどういう理由で素数扱いされて入ってきたのでしょうか?
1時間くらいいろいろ調べて動かして考えたましたが、原因がさっぱり分からないので、理由や今後の類似事象の予防策など教えてください。

以下のような質問にはグッドを送りましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

グッドが多くついた質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

回答2

2

ベストアンサー

配列をグローバルで宣言した時の仕様は、以下の質問を参考にしてください。
https://teratail.com/questions/168427

バグの理由は、配列の初期化をしていないからです。

C++

1//5行目~ 2void _main() { 3int prime[210]; //(a) 4for(int i=2;i<=210;i++){ 5 bool p=true; 6 for(int j=2;j<=sqrt(i);j++){ 7 if(i%j==0)p=false; 8 } 9 if(p)prime[i]=1; //(b) 10} 11for(int i=0;i<210;i++){if(prime[i]==1)cout<<i<<' ';} //(c) 12}

(a)の時点では初期化をしていないので、配列の各要素の値は不定です。 (b)でiが素数の場合は1を代入していますが、合成数の場合は代入されず、(c)で初期化されていない要素の値を得ようとしているので、バグが発生します。

(a)をint prime[210] = {};に書き換えるか、(b)でiが合成数だった場合は0を代入する等で、全ての要素が初期化されるようにしてください。

また、C++を使うのであれば、vectorを使うことをおすすめします。配列を定義するときに任意の値で要素の初期化を行うことができ、未初期化によるバグの発生も防げます。

コード例:

C++

1#include<bits/stdc++.h> 2using namespace std; 3void _main(); int main() { _main(); } 4 5void _main() { 6 vector<int> prime(210, 0); //210個のint型要素を持つ配列を定義、各要素を0で初期化 7 for(int i=2;i<=210;i++){ 8 bool p=true; 9 for(int j=2;j<=sqrt(i);j++){ 10 if(i%j==0){ 11 p=false; 12 break; 13 } 14 } 15 if(p)prime[i]=1; 16 } 17 for(int i=0;i<210;i++){if(prime[i]==1)cout<<i<<' ';} 18}

投稿2022/02/19 15:48

編集2022/02/19 16:00
luuguas

総合スコア453

yudedako67, Kinsho👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

Kinsho

2022/02/20 04:27

参考リンクをありがとうございます。 勉強になりました。 次からは初期化を忘れないようにします。

1

ローカル変数の場合、配列のナカミの初期値は不定です。

if(p)prime[i]=1;

prime[i]= p ? 1 : 0;
に変更してはいかがか。

[追記] 僕ならこう書く:

C++

1#include <iostream> 2#include <cmath> 3 4int main() { 5 bool prime[210]; 6 for ( int i = 2; i <= 210; ++i ) { 7 bool& p = prime[i]; 8 p = true; 9 for( int j = 2, limit = sqrt(i); j <= limit; ++j ) { 10 if ( i % j == 0 ) { 11 p = false; 12 break; 13 } 14 } 15 } 16 for ( int i = 2; i < 210; ++i ) { 17 if ( prime[i] ) std::cout << i << ' '; 18 } 19}

投稿2022/02/20 00:51

編集2022/02/20 01:02
episteme

総合スコア16009

Kinsho👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

Kinsho

2022/02/20 04:27

ローカル変数の危険性について勉強できました。 ありがとうございました

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
86.02%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。