Fastest algorithm for primality test

c++ algorithm math primes
dada picture dada · Apr 6, 2010 · Viewed 36.7k times · Source

I need to test primality on intervals between numbers which are really big (in the range of long long), so i need some fast algorithm for checking if a number is prime or not. Please suggest your ideas.

Answer

cobbal picture cobbal · Apr 6, 2010

One good method is the Miller-Rabin test. It should be noted however, that this is only a probabilistic test.

Related questions

Fast ceiling of an integer division in C / C++

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3. The …

Read More
Creating all possible k combinations of n items in C++

There are n people numbered from 1 to n. I have to write a code which produces and print all different combinations of k people from these n. Please explain the algorithm used for that.

Read More
Finding square root without using sqrt function?

I was finding out the algorithm for finding out the square root without using sqrt function and then tried to put into programming. I end up with this working code in C++ #include <iostream> using namespace std; double …

Read More