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

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

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

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

C++

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

Q&A

解決済

2回答

957閲覧

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

Kinsho

総合スコア18

アルゴリズム

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

C++

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

0グッド

0クリップ

投稿2022/02/19 15:00

編集2022/02/20 13:27

競技プログラミングの問題を解いているときに約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時間くらいいろいろ調べて動かして考えたましたが、原因がさっぱり分からないので、理由や今後の類似事象の予防策など教えてください。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

配列をグローバルで宣言した時の仕様は、以下の質問を参考にしてください。
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

総合スコア492

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Kinsho

2022/02/20 04:27

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

0

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

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

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Kinsho

2022/02/20 04:27

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問