C++でN以下のすべての素数を出力する方法を解説

問題概要

この問題では、整数Nが与えられ、N以下のすべての素数を出力することが求められます。

入出力例

入力: 10
出力: 2 3 5 7

素数とは

素数とは、1とその数自身でのみ割り切れる正の整数のことです。たとえば、2、3、5、7などが該当します。

単純なアプローチ

最も簡単な方法は、2からNまでの各数値について、それより小さい数で順番に割っていき、どこでも割り切れなければ素数として出力するやり方です。これをNに達するまで繰り返します。ただし、この方法は1つの数を判定するのに大量の除算が必要となるため、効率面で課題があります。

効率的なアプローチ

より効果的なのが、素数判定を「2から√Nまで」の範囲で行う方法です。合成数は必ず√N以下の約数を持つため、そこまで調べれば十分に判定できます。さらに、2と3で割り切れるかを先にチェックしたうえで、6ずつ増やしながら「i」と「i+2」（6k±1の形の数）だけを試すことで、無駄な除算を減らし処理を高速化しています。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
 
bool isPrimeNumber(int n){
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}
 
void printPrime(int n){
    for (int i = 2; i <= n; i++) {
        if (isPrimeNumber(i))
            cout << i << " ";
    }
}
 
int main(){
    int n = 41;
    cout << n << " 以下の素数は次の通りです\n";
    printPrime(n);
}

コードのポイント

• isPrimeNumber関数: 素数判定を行います。nが1以下なら素数ではない、2と3は素数、2または3で割り切れる場合は素数ではない、と順に判定します。
• 6k±1の最適化: 5から開始してiを6ずつ増やしながらiとi+2のみ確認することで、判定回数を大幅に削減しています。
• printPrime関数: 2からnまでの各数に対して素数判定を行い、素数だけを出力します。

実行結果

41以下の素数は以下の通りです。

2 3 5 7 11 13 17 19 23 29 31 37 41

まとめ

このアルゴリズムの素数判定1回あたりの計算量はO(√N)、全体ではO(N√N)となります。なお、「N以下の素数をすべて列挙する」用途にはエラトステネスの篩（ふるい）を使うとO(N log log N)でより高速に求められるため、Nが大きい場合におすすめです。