C++における素数判定法

方法1: ループによる判定 この方法では、2から対象の数の平方根までの数で割り切れるかどうかを判定します。割り切れる場合は素数ではありません。

#include <iostream>
#include <cmath>
bool isPrime(int number) {
   if (number < 2) {
       return false;
   }
   for (int i = 2; i <= sqrt(number); i++) {
       if (number % i == 0) {
           return false;
       }
   }
   return true;
}
int main() {
   int num;
   std::cout << "数を入力してください: ";
   std::cin >> num;
   if (isPrime(num)) {
       std::cout << num << " は素数です。" << std::endl;
   } else {
       std::cout << num << " は素数ではありません。" << std::endl;
   }
   return 0;
}

方法2: エラトステネスのふるい エラトステネスのふるいは、ある範囲内の数の中で素数を見つけるための効率的なアルゴリズムです。以下にコード例を示します。

#include <iostream>
#include <vector>
void sieveOfEratosthenes(int n) {
   std::vector<bool> isPrime(n + 1, true);
   for (int p = 2; p * p <= n; p++) {
       if (isPrime[p] == true) {
           for (int i = p * p; i <= n; i += p) {
               isPrime[i] = false;
           }
       }
   }
   for (int p = 2; p <= n; p++) {
       if (isPrime[p]) {
           std::cout << p << " ";
       }
   }
   std::cout << std::endl;
}
int main() {
   int num;
   std::cout << "範囲の上限を入力してください: ";
   std::cin >> num;
   std::cout << "素数: ";
   sieveOfEratosthenes(num);
   return 0;
}