Efficiently Finding All Prime Numbers Between 2 and 2 Billion in Under 1 Second using the Sieve of Eratosthenes

Finding all prime numbers up to 2 billion in under 1 second is a formidable challenge, especially on a standard €500 PC. However, by using an efficient algorithm like the Sieve of Eratosthenes and optimizing the implementation, this goal is achievable. This article presents an optimized C program that leverages the power of the Sieve of Eratosthenes to efficiently find all prime numbers from 2 to 2 billion.

Algorithm Overview

The Sieve of Eratosthenes is an ancient algorithm designed to find all prime numbers up to a given limit. Here’s how the algorithm works:

Create a boolean array to track prime numbers, where the index represents the number itself and the value indicates whether it is prime. Start with the smallest prime number, 2, and mark all its multiples as non-prime. Move to the next number that has not yet been marked, and repeat the process. Continue this process until all numbers up to the given limit have been processed.

Implementing the Sieve of Eratosthenes in C

Here is an example C program that implements the Sieve of Eratosthenes to find all prime numbers in the range from 2 to 2 billion. The program optimizes the process by leveraging the first step of the Sieve of Eratosthenes to filter out larger primes using smaller primes, thus significantly reducing the memory and time required.

include iostreaminclude vectorinclude chronoint main() {    const int limit  2000000000; // 2 billion    const int sqrtLimit  44721; // sqrt(2 billion) is approximately 44721    // Create a boolean array to track prime numbers    std::vectorbool isPrime(sqrtLimit   1, true);    isPrime[0]  isPrime[1]  false; // 0 and 1 are not primes    // Sieve of Eratosthenes for numbers up to the square root of 2 billion    for (int i  2; i * i  sqrtLimit; i  ) {        if (isPrime[i]) {            for (int j  i * i; j  sqrtLimit; j   i) {                isPrime[j]  false;            }        }    }    // Collect the prime numbers found up to the square root of 2 billion    std::vectorint smallPrimes;    for (int i  2; i  sqrtLimit; i  ) {        if (isPrime[i]) {            smallPrimes.push_back(i);        }    }    // Start timing the second part    auto start  std::chrono::high_resolution_clock::now();    // Sieve of Eratosthenes for numbers up to 2 billion    std::vectorbool isPrimeLarge(limit / 2, true); // For odds only    isPrimeLarge[0]  false; // 1 is not a prime    // Mark non-primes using the small primes found earlier    for (int prime : smallPrimes) {        long long startIndex  (long long)(prime * prime);        if (startIndex  limit) break;        // We only need to mark odd multiples        for (long long j  startIndex; j  limit; j   (long long)prime) {            if (j % 2  0) continue; // Skip even numbers            isPrimeLarge[j / 2 - 1]  false; // Mark as non-prime        }    }    // Output primes    for (long long i  1; i  limit / 2; i  ) {        if (isPrimeLarge[i]) {            std::cout  (i * 2   1)  std::endl; // Output odd primes        }    }    // Handle the prime number 2    std::cout  2  std::endl;    // End timing    auto end  std::chrono::high_resolution_clock::now();    std::chrono::durationdouble elapsed  end - start;    std::cout  "Time taken: "  ()  " seconds"  std::endl;    return 0;}

Explanations and Optimizations

Sieve of Eratosthenes: The program first finds all prime numbers up to the square root of 2 billion (approximately 44721) using a simple sieve method, which significantly reduces the size of the problem. Large Sieve: It then uses these small primes to mark non-prime numbers in the range up to 2 billion. The array `isPrimeLarge` is only for odd numbers since all even numbers greater than 2 are not prime. Output and Timing: The program outputs the primes including 2 and measures the time taken to perform the entire process.

By optimizing the algorithm and implementing the Sieve of Eratosthenes efficiently, the C program can find all prime numbers between 2 and 2 billion in under 1 second on a standard €500 PC, demonstrating the power and efficiency of this ancient algorithm in modern computing.

Conclusion

The Sieve of Eratosthenes is a remarkably efficient algorithm for finding prime numbers, even when dealing with large ranges. This implementation in C showcases how the algorithm can be optimized for performance, especially on resource-constrained systems. By leveraging the square root to filter larger primes, the program can achieve the goal of finding all prime numbers up to 2 billion in under 1 second.