为什么这个 Fermat 素数测试器给我一个例外？

Question

为什么这个费马素性测试仪给我一个例外？

class PrimeTest
{
    public static bool IsPrime(long n, int iteration = 5)
    {
        Random r = new Random();
        long a = 0;
        long aPow = 0;

        for (int i = 0; i < iteration; i++)
        {
            a = r.Next(1, Convert.ToInt32(n - 1));

            double x = Convert.ToDouble(a);
            double y = Convert.ToDouble(n - 1);
            double p = Math.Pow(x, y);

            aPow = Convert.ToInt64(p);//<==== this line is giving an exception.

            if (1 % n == aPow % n)
            {
                return true;
            }
        }

        return false;
    }
}

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine("{0}", PrimeTest.IsPrime(33));
        Console.ReadLine();
    }
}

输出

An unhandled exception of type 'System.OverflowException' occurred in mscorlib.dll

Additional information: Arithmetic operation resulted in an overflow.

Answer 1

运行你的程序，我得到：

3.4336838202925124E+30，或3433683820292512400000000000000

Int64 或 long 的最大值是 9223372036854775807

很容易看出您获得 Overflow Exception 的原因。如果您查看消息，您会看到更多详细信息：

Arithmetic operation resulted in an overflow.

这个数字太大，无法放入 long 值。

Answer 2

你的a是随机数[1~n-1]，a^(n-1)很容易大于Int64.Max 例如，a=10 和 10^32 大于 Int64.Max.

        Random r = new Random();
        long a = 0;
        long aPow = 0;

        for( int i = 0; i < iteration; i++ ) {
            a = r.Next( 1, Convert.ToInt32( n - 1 ) );

            // p is 1E32; if a==10
            double p = Math.Pow( Convert.ToDouble( a ), Convert.ToDouble( n - 1 ) );

            // Int64 is 9223372036854775807, which is less than 1E32
            aPow = Convert.ToInt64( p ); //giving exception

            if( 1 % n == aPow % n ) {
                return true;
            }
        }

        return false;

为什么这个 Fermat 素数测试器给我一个例外？

Why is this Fermat primality tester giving me an exception?

c#

primes