Originally Posted by

**amberxinya** the problem is, devise the most efficient algorithm to determine primality <1000000. show this by comparing the times taken by different algorithms.

i made a trial division, fermat test, euler test, euler-jacobi test, miller rabin test.

and i think a trial division + miller rabin will be the most efficient.

so i ran my program < 100000 and timed it , it costs 20 sec.

for miller rabin base 2 and base 3 , the time is 50 sec.

BUT, for those other methods, their times are less than 5 sec.

So how could trial division + miller rabin be the most efficient way?