素数判定法

どういうわけか素数を判定するプログラムを書こうと思った。
そこでミラーラビン法をC言語(VC++ 2005)で書いた。
ところが、
9と15が合成数（非素数）であることを見破れない。
9と15は強擬素数（判別の難しい合成数）でもないはずだが。。。
さらに、OverflowException算術演算の結果オーバーフローが発生してしまう。
原因はpow( )を使っているためだろう。
pow(int, int)の引数を持つオーバーロード関数が無いことといい、全くもって使えない。




9と15の問題点についてはエラトステネスの篩で落とせるだろう。
そう思って書こうとしたが、これが以外に難しい。
有名なアルゴリズムなので簡単だと思っていたのだが。


ソースを置いてみますが、書いた本人にも正しいのか間違っているのか
不明な代物ですので、そこんとこのご承知を。
WikipediaにはRuby版のミラーラビン法ソースコードがありますよ。

#include "stdafx.h"

#include 

#include 

#include 

#include 
using namespace System;
bool millerrabin(int, int);


int main(array ^args)

{

    for (int sn = 2; sn < 25; sn++) {

        bool b = millerrabin(sn, 1000);

        Console::Write("{0}は", sn);

        if (b) Console::WriteLine("素数です");

        else Console::WriteLine("合成数です");

    }
    Console::WriteLine("\n\n\n\n\n\n");

    return 0;

}
bool millerrabin(int n, int k) {

	if (n <= 1) return false;

	if (n%2 == 0) return false;

	int s = 0, d = n - 1;

	while (d%2 == 0) {

		d /= 2;

		s++;

	}

//	Console::WriteLine("d={0}, s={1}", d, s);

	for (; k>0; k--) {

		srand(time(NULL));

		int a = rand() % (n - 2) + 1;

		if ((int)pow((float)a, d) % n == 1) return false;

		for (int r=0; r