素数判定ルーチン
ちょっと組み込みマイコンで必要になったので、整数演算のみを使って高速かつコンパクトな9桁(10億)以下の素数を判定するルーチンを作った。
引数に10億以下の自然数を入れて呼ぶ。素数ならば返値として非ゼロ(≠0)を返す。ゼロ(=0)の場合は合成数。
一応、9桁範囲での全ての値でチェックをしてますが、使用は自己責任でお願いします。
引数に10億以下の自然数を入れて呼ぶ。素数ならば返値として非ゼロ(≠0)を返す。ゼロ(=0)の場合は合成数。
#include <stdio.h> #include <inttypes.h> /* 素数かどうか判定 */ int isPrime(const uint32_t number) { uint32_t x, y, n; int i; // numberが2以下と偶数の場合を除去 if (!(number & 1) || number < 2) return (number == 2); // 二進開平法でnumberの整数平方根を計算 x = number; i = 0; while(x >>= 1) i++; i += i & 1; x = number; n = y = 0; for(; i >= 0 ; i -= 2) { n <<= 1; y <<= 1; if ((y | 1) <= (x >> i)) { n |= 1; y |= 1; x -= y << i; y++; } } // 約数のチェック for(x = 3 ; x <= n ; x += 2) { if ((number % x)== 0) { x = 0; break; } } return (x != 0); }
一応、9桁範囲での全ての値でチェックをしてますが、使用は自己責任でお願いします。
2018-02-09 02:27