Accurate "Sieve of Erathostenes" to determine primality of BigInteger in C#

Question

The problem I am trying to solve is to find the primality of an arbitrarily long number (BigInteger) in C#. To achieve this task, I have implemented the "Sieve of Erathostenes". The algorithm is already fast, but in terms of accuracy, I am skeptical as I am unsure of how accurate BigInteger is in representing arbitrarily long numbers.

The "Sieve of Erathostenes" algorithm

public static bool IsPrime(BigInteger value)
{
    int result = 0;
    // 2, 3, 5 and 7 are the base primes used in the Sieve of Erathostenes
    foreach (int prime in new int[] { 2, 3, 5, 7 })
    {
        // If the value is the base prime, it's prime - no further calculation required.
        if (value == prime)
        {
            return true;
        }

        // Else, we need to work out if the value is divisible, by any of these primes...
        BigInteger remainder = 0;
        BigInteger.DivRem(value, prime, out remainder);

        if (remainder != 0)
        {
            // We increment result to indicate that the value was not divisible by the base prime
            result++;
        }
    }

    // If result is 4, thus, not divisible my any of the base primes, it must be prime.
    return result == 4;
}

My question is not "why is my code not working" - it's more "is this accurately determining primality of BigInteger"

Specifically, I would like to know about the accuracy of BigInteger.DivRem

Answer 1

Sieve of Erathostenes is work as follow:

• First assume that all numbers is prime.

• Starting from 2, crossing out all the numbers that is a multiple of two. Then, move to the next number that is not crossed out, and remove all multiple of this number, and so on... so, in the end what is left is the list of prime number.

So clearly, your code is not Sieve of Erathostenes, which you made an assumption that the list of prime is only 2,3,5,7

To check whether a number is a prime or not, we can have a more easy way, instead of using Sieve of Erathostenes, which is only suitable when you want to generate a list of prime numbers.

Pseudo Code:

boolean isPrime(int num){

    for(int i = 2; i*i <= num ; i++){
        if(num % i == 0){
           return false;
        }            
    }
    return true;
}