本記事では入力した値以下の素数を出力するプログラムを紹介します。
素数を求めるプログラム
素数とは1と自分以外に約数を持たない数のことです。
2, 3, 5, 7... などが素数になります。
ある値が素数かどうかプログラムで出力するには下記の関数のように、
「2 ~ ある値 - 1」の数までで割り切ることができる数がなければ素数であると判定することができます。
#include <iostream>
using namespace std;
bool isPrimeNum(int num){
for (int i = 2; i < num; ++i){
if (num % i == 0){
return false;
}
}
return true;
}
上記の関数を使い2~入力値まで順番に素数かどうか判定することで、入力した値以下の素数を全て出力することができます。
int main(void){
int num;
cin >> num;
for (int i = 2; i <= num; ++i){
if (isPrimeNum(i)){
cout << i << endl;
}
}
return 0;
}
プログラムを高速化する
先ほど紹介したプログラムは計算量がで効率が良いプログラムとは言うことができません。
そこでここでは先ほどのプログラムを高速化していきます。
まずはisPrimeNum関数を最適化しています。
先ほどのisPrimeNum関数では「2 ~ ある値 - 1」の数までで割り切ることができる数がなければ素数であると判定していましたが、ある値が素数であるかどうか判定するには「ある値未満の素数」で割ることができるか計算するだけで大丈夫です。
なのでisPrimeNum関数を以下のように書き換えてしまいましょう。
bool isPrimeNum(int num){
static vector primeNumVec = {2};
for (auto itr = primeNumVec.begin(); itr != primeNumVec.end(); ++itr){
if (num % *itr == 0){
return false;
}
}
primeNumVec.push_back(num);
return true;
}
primeNumVecというベクターに素数と判定した数をため込んで、入力値がprimeNumVecの中の値で割り切れるかどうか判定します。
これだけでも十分早くなるのですが、main関数にも一工夫加えていきます。
素数は2以外の値は全て奇数なので、for文のiを1ずつ増やしてすべての数を見るのではなく、iを2ずつ増やして奇数だけを見るようにしましょう。
int main(void){
int num;
cin >> num;
cout << 2 << endl;
for (int i = 3; i <= num; i+=2){
if (isPrimeNum(i)){
cout << i << endl;
}
}
return 0;
}
これで入力した値以下の素数を出力するプログラムを高速化することができました。
最後に
本記事を通して素数を求めるプログラムの作り方が分かりましたか。
他にもプログラムに関する記事を書いていますので興味のある方はぜひ読んでみてください。