とりあえず、一番簡単そうな方法で実装してみた。 …まあ、こう言っては何だけど、もっとちゃんとした方法で作るべきみたいだね。
/** * @file prime.hpp * @brief テーブルを利用した素数判定クラス */
#ifndef _PRIME_HPP_ #define _PRIME_HPP_
// ヘッダ・ファイル #include <vector> #include <cmath>
/** * @brief テーブルを利用した素数判定クラス * @note UINT_TYPE には (unsigned 系の) 整数型を適用すること。 */ template<typename UINT_TYPE> class PrimeChecker { // 型 private:
typedef std::vector<UINT_TYPE> TABLE_TYPE; /// テーブルの型 typedef typename TABLE_TYPE::size_type SIZE_TYPE; /// テーブルの幅の型
// インスタンス・フィールド private:
TABLE_TYPE primes_; /// 奇数の素数によるテーブル UINT_TYPE next_check_; /// 素数テーブル追加探索をまだしてない最小奇数
// インスタンス・メソッド public:
/** * @brief デフォルト・コンストラクタ * @note 最小のテーブル {3} により構成される。 */ inline PrimeChecker(void) : primes_(1, 3), next_check_(5) { ; }
/** * @brief 引数 number 以下の全ての素数を含むようにテーブルを拡張 * @param number [in] テーブルを拡張する際の素数の上限 * @return テーブルに格納されてる最大の素数 * @note 引数 number が既存のテーブルの最大素数より小さい場合、 * 何も起こらない。 */ inline void extendTable(const UINT_TYPE number) { UINT_TYPE sqrt_target; SIZE_TYPE i; bool divisible; UINT_TYPE target(next_check_); while (target <= number) { sqrt_target = std::sqrt(target); divisible = false; for (i = 0; primes_[i] <= sqrt_target; ++i) { if (target % primes_[i] == 0) { divisible = true; break; } } if (!divisible) { primes_.push_back(target); } target += 2; } next_check_ = target; }
/** * @brief テーブルを構築できるコンストラクタ * @param number [in] テーブルを拡張する際の素数の上限 */ inline PrimeChecker(const UINT_TYPE number) : primes_(1, 3), next_check_(5) { extendTable(number); }
/** * @brief 素数か否かのチェック * @param target [in] チェック対象の数 * @return * - true: 引数 target は素数 * - false: 引数 target は合成数か、1 以下の数 */ inline bool checkPrime(const UINT_TYPE target) { if (target % 2 == 0) return target == 2; if (target < 2) return false; SIZE_TYPE i(0); SIZE_TYPE size = primes_.size(); while (i < size) { if (target % primes_[i] == 0) { return target == primes_[i]; } ++i; } UINT_TYPE divisor(next_check_); const UINT_TYPE sqrt_target = std::sqrt(target); while (divisor <= sqrt_target) { for (i = 0; i < size; ++i) { if (divisor % primes_[i] == 0) break; } if (i >= size) { primes_.push_back(divisor); ++size; if (target % divisor == 0) { next_check_ = divisor + 2; return false; } } divisor += 2; } next_check_ = divisor; return true; } };
#endif // _PRIME_HPP_
ついでにこのクラスを試用するためのコマンド。
/** * @file main.cpp * @brief 素数の個数を算出するコマンド */
// ヘッダ・ファイル #include <iostream> #include <cctype> #include "prime.hpp"
// 名前の解決 using namespace std;
/** * @brief 使用方法の表示 * @param command [in] コマンド名 */ void PrintUsage(const char* const command) { cerr << "Usage: " << command << " [integer (>1)]" << endl; }
/** * @brief 素数の個数を算出するコマンド */ int main(int arg_count, char** arg_strings) { // 引数のチェック int max_value(10000000); if (arg_count > 2) { PrintUsage(arg_strings[0]); return -1; } else if (arg_count == 2) { const char* arg_string = arg_strings[1]; while (*arg_string != '\0') { if (isdigit(*arg_string) == 0) { PrintUsage(arg_strings[0]); return -2; } ++arg_string; } max_value = atoi(arg_strings[1]); if (max_value <= 1) { PrintUsage(arg_strings[0]); return -3; } }
// 計算開始の出力 clog << "Calculating..." << endl;
// 素数チェッカーの準備 PrimeChecker<int> pchecker;
// 素数のチェック size_t number_of_results(0); int i(1); int largest_prime(2); do { ++i; if (pchecker.checkPrime(i)) { ++number_of_results; largest_prime = i; } if (i % 10000000 == 0) { clog << "> " << number_of_results << " primes exist... (" << i << '/' << max_value << ')' << endl; } } while (i < max_value);
// 結果の出力 clog << number_of_results << " primes exist in {1, ..., " << max_value << "}.\n" << largest_prime << " is largest prime in {1, ..., " << max_value << "}." << endl;
return 0; }
残念ながら、「動いてるかな?」程度の成果物。
$ g++ -Wall -O3 main.cpp -o primes
$ time ./primes 2147483647
[...]
105097565 primes exist in {1, ..., 2147483647}.
2147483647 is largest prime in {1, ..., 2147483647}.
6709.182u 9.502s 1:52:02.18 99.9% 0+0k 0+2io 0pf+0w
この結果で当ってるのかな?
少しいじってみた。
PrimeChecker::checkPrime() で算出した数値の再利用は実装してない。
もちろん、テスト用と位置付けてる main() の方で工夫する気はない。
$ g++ -Wall -O3 main.cpp -o primes
$ time ./primes 2147483647
[...]
105097565 primes exist in {1, ..., 2147483647}.
2147483647 is largest prime in {1, ..., 2147483647}.
6597.111u 12.122s 1:50:23.99 99.7% 0+0k 0+0io 0pf+0w
10/13 発売予定の新作。 けっこう久々だったかな。
Mac で Mac OS X と Windows の dual boot を実現するためのツール。 所謂人柱版。
本質的なシンプルさを備えているスクリプト言語。 所謂人柱版。
複数の文字コードに対応した C の正規表現ライブラリ (BSD ライセンス)。 約 2 週間ぶりの version up。