Prime number checker

Writing a general algorithm to check if a (positive integer) number is a prime is a too complicated matter to be discussed here (and to be asked as a interview question for a programmer position). Have a look at the Manindra Agrawal, Neeraj Kayal, Nitin Saxena document where they "present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite", friendly known as AKS algorithm, to see what I mean.

Still, if our requirements are not very strict, and we are happy enough with a function that has reasonable performance only for small numbers, it is a different matter.

A couple of thousands years ago, a very smart guy named Eratosthenes of Cyrene had prime numbers among his many interests. He devised the algorithm known as the sieve of Eratosthenes that could still make sense to use.

The algorithm is designed to return all the prime numbers in an interval, so using it to check just a single number is a kind of an overkill. About the same of what happens for similar algorithm to calculate factorial or Fibonacci numbers.

I want to write a function following this declaration and passing the below stated test case:
bool isPrime(unsigned long long value); // 1

TEST(TestPrime, Eratosthenes)
{
    EXPECT_FALSE(isPrime(42));
    EXPECT_TRUE(isPrime(977));
    EXPECT_TRUE(isPrime(4987));
    EXPECT_FALSE(isPrime(999999997));
    EXPECT_TRUE(isPrime(32416190071));
    EXPECT_TRUE(isPrime(99494896918097));
    EXPECT_TRUE(isPrime(997080383502859));
    EXPECT_TRUE(isPrime(2305843009213693951)); // 2
}
1. I'd like my function to be able to manage very big numbers. It should accept a not negative huge integer in input and answer with a boolean.
2. This 19 digits integer is known as Mersenne M61, or Pervushin's number, we know it is a prime number since 1883, and I could consider myself happy if my function could check it in a reasonable time.

Here is how I implemented the solution:
bool isPrime(unsigned long long value)
{
    if(value < 2) // 1
        return false;
    if(value < 4)
        return true;
    if(value % 2 == 0)
        return false;

    long max = static_cast<long>(std::ceil(std::sqrt(static_cast(value)))); // 2

    for(long i = 3; i <= max; i += 2) // 3
        if(value % i == 0) // 4
            return false;

    return true;
}
1. Get rid of trivial cases. Zero and one are not considered prime numbers; two and three are OK; all the even number bigger than two are not prime.
2. Optimization. If we want to check if 101 is a prime number, we don't have to check all the previous number till 100, we can stop checking an awful long before. It is enough to check till the next integer after its square root (and if you think about it, you should understand why).
3. Let's loop. We need to check for all the possible odd divisors starting from three. Actually, we don't really need to check a lot of them, like nine (being a multiple of three), but there is no cheap way of keeping track of which one has to be checked and which not. It is easier doing in this way.
4. Divide our input number for the current candidate. It could be the end of our job, otherwise try the next one.

No comments:

Post a Comment