はじめに
この記事はプログラム、数学初心者向けです。私自身のメモでもあります。
誤りなどがありましたらぜひお知らせください。プログラムはそのままコピペで試すことが可能だと思います。
例えばこちらなど >> paiza
素数とは
- $1$ と自分自身以外に約数を持たない数
- 約数が $2$ 種類の数
どちらも同じ意味になります。$1$ は約数が $1$ つしかないので、素数ではありません。
約数はその数を割り切れる数です。$15$ の約数は $1,3,5,15$ となります。
シンプルな判定方法
ある数 $n$ が素数かどうかを知りたい。
$2 \sim (n-1)$ で割ってみて割り切れたら素数ではない、割り切れなかったら素数という方法。
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i < (n); i++)
using namespace std;
using ll = long long;
// 素数であればtrue、素数でなければfalseを返す
bool prime(int n){
// 0,1の場合は素数ではない
if(n<2) return false;
// 2~n-1で実際に割って確認する
for(int i=2; i<=n-1; i++){
if(n%i == 0){
return false;
}
}
// １と自分自身以外で割り切れる数が無かったので素数
return true;
}
int main(){
int n=3457;
if(prime(n)){
cout << n << "は素数である" << endl;
}else{
cout << n << "は素数ではない" << endl;
}
}
素数の判定を少し工夫してみる
実は$2 \sim (n-1)$まで試さなくてもよい。例えば $100$ を割っていくと積のペアは以下のようになる。
(1,100), (2,50), (4,25), (5,20), (10,10), (20,5), (25,4), (50,2), (100,1)
よく見ると、
(4,25), (25,4)
は同じ積に分けられているので実際は $10$ まで確認するとすべてのペアが出そろうことが分かる。厳密な証明は省くが、ある数 $n$ に対して
\sqrt{n}
までチェックすればよい。先ほどのコードを書き換えてみる。
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i < (n); i++)
using namespace std;
using ll = long long;
// 素数であればtrue、素数でなければfalseを返す
bool prime(int n){
// 0,1の場合は素数ではない
if(n<2) return false;
// √n まででよいということは i*i<=n までチェックすることと同じ
for(int i=2; i*i<=n; i++){
if(n%i == 0){
return false;
}
}
// １と自分自身以外で割り切れる数が無かったので素数
return true;
}
int main(){
int n=1'000'000'007;
if(prime(n)){
cout << n << "は素数である" << endl;
}else{
cout << n << "は素数ではない" << endl;
}
}
コードは本当にわずかの違いであるが、例えば、
1000000007 \quad (10^9+7)
は素数であるが、最初のコードでは $10^9$ 程度のループが回ってしまい、とても時間がかかってしまう。
しかし、改善したコードでは多く見積もっても $10^5$ 程度なので十分高速に判定ができる。
エラトステネスの篩
何度も判定する場合はあらかじめ素数を調べておくという方法がある。
$n$ 以下の素数を全て調べることを考えてみる。まず、$2 \sim n$までの整数を並べる。(例：$n=30$ とする）
\bigl\{2,3,4,5,・・・,30 \bigr\}
まず $2$ の倍数を取り除く。（ $2$ は取り除かず、$4 \sim $ を取り除く）
\bigl\{2,3,5,7,9,11,13,15,17,19,21,23,25,27,29 \bigr\}
次に $3$ の倍数を取り除くと、
\bigl\{2,3,5,7,11,13,17,19,23,25,29 \bigr\}
次に $5$ の倍数を取り除くと、
\bigl\{2,3,5,7,11,13,17,19,23,29 \bigr\}
そして $7$ の倍数は実は $\sqrt{30} < 7$ なのでチェックする必要がない。つまり $30$ 以下の素数は上のすべてである。プログラムで実装する際は予め大きさが $n$ の配列を持っておいて配列の番地を利用してチェックしてくとよい。
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i < (n); i++)
using namespace std;
using ll = long long;
void Eratosthenes(vector<int> &vec){
// 0と1は素数ではない
vec[0]=0; vec[1]=0;
// 篩を行う
for(int i=2; i*i < vec.size(); i++){
// すでに素数でないことが分かっている。除外されている場合の数はスルーする。
if(vec[i]==0) continue;
int x = i+i;
while(x < vec.size()){
// iの倍数は除外していく。素数でないので0にする。
vec[x]=0;
x += i;
}
}
}
int main(){
int n=5000000;
// エラトステネスの篩ようの配列、初期値を１（素数）としておく。
vector<int> vec(n+1,1);
Eratosthenes(vec);
// mが素数かどうか判定
int m=19999;
if(vec[m]){
cout << "素数" << endl;
}else{
cout << "素数でない" << endl;
}
// 0～100までの素数を出力してみる
for(int i=0; i<=100; i++){
if(vec[i]) cout << i << " ";
}
}
エラトステネスの篩の計算量は $O(n\log \log n)$ なので $n=10^9$ とするとだいぶ時間がかかってしまうが、一度計算してしまうと $n$ 以下の数は $O(1)$ で判定できるので非常に強力である。