C++ | 素数ジェネレータの実装例

C++ での素数ジェネレータの実装例を紹介します。

PrimeNumberGenerator のクラスインスタンスを生成し、 ()演算子を呼び出すことで無限に素数を生成することができます。

#include <iostream>
#include <vector>

class PrimeNumberGenerator
{
public:
    PrimeNumberGenerator() : ps_(std::vector<unsigned long>{2}) {}

    unsigned long operator()()
    {
        auto curr = ps_.back();
        auto next = curr + 1;
        while (true)
        {
            if (is_prime(next))
            {
                ps_.push_back(next);
                return curr;
            }
            ++next;
        }
    }

    bool is_prime(unsigned long n) const
    {
        for (auto p : ps_)
        {
            if (p * p > n)
            {
                return true;
            }
            if (n % p == 0)
            {
                return false;
            }
        }
        throw std::runtime_error("unexpected error");
    }

private:
    std::vector<unsigned long> ps_;
};

int main()
{
    PrimeNumberGenerator png;
    for (std::size_t i = 0; i < 100; ++i)
    {
        std::cout << png() << ", ";
    }
    std::cout << std::endl;
    return 0;
}
$ g++ prime.cc && ./a.out
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 
  • URLをコピーしました!
  • URLをコピーしました!

コメント

コメントする

このサイトは reCAPTCHA と Google によって保護されていますプライバシーポリシー利用規約 申し込み。

The reCAPTCHA verification period has expired. Please reload the page.

目次