So-net無料ブログ作成

素数判定ルーチン

ちょっと組み込みマイコンで必要になったので、整数演算のみを使って高速かつコンパクトな9桁(10億)以下の素数を判定するルーチンを作った。
引数に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桁範囲での全ての値でチェックをしてますが、使用は自己責任でお願いします。