C Program to Implement Sieve of Eratosthenes
The Sieve of Eratosthenes is a simple and efficient algorithm for finding all prime numbers up to a specified integer. It was created by the ancient Greek mathematician Eratosthenes and is still used today due to its efficiency when dealing with large numbers.
In this article, we will learn how to implement sieve of Eratosthenes in C.
Implementation of the Sieve of Eratosthenes in C
To get started, we go through each number from 2 onwards marking off its multiples as composite numbers (not prime). This is repeated for every prime found.
Algorithm
- To start, make a list of prime[] having n+1 indices with each having true, where true represents the index has a prime number.
- Since 0 and 1 are not prime numbers, set prime[0] and prime[1] to false.
- Starting from 2, for i=2, is i contained in prime[]? If yes, then proceed: true means it is a prime number otherwise it is not so skip all other steps that follows and move to the next i. After that go through all multiples of i (like i*i, i*i+i, i*i+2i,…) such that each multiple is less than or equal to n and make them false in the list.
- Similarly find all multiples which are less than or equal to n and set them false in prime[] array.
- Do the above process until you reach sqrt(n). Any index that is still marked as true in the list, shows that number is a prime one.
The above method is not only easy but it also works very efficiently especially when you want to find all prime numbers below any given maximum limit
C Program to Implement Sieve of Eratosthenes
Below is an example of a C program implementing the sieve of Eratosthenes:
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// Define SieveOfEratosthenes function
void SieveOfEratosthenes(int n)
{
// Allocate memory for prime array and initialize all
// elements as true
bool* prime = malloc((n + 1) * sizeof(bool));
for (int i = 0; i <= n; i++)
prime[i] = true;
// 0 and 1 are not prime numbers
prime[0] = prime[1] = false;
// For each number from 2 to sqrt(n)
for (int p = 2; p <= sqrt(n); p++) {
// If p is prime
if (prime[p]) {
// Mark all multiples of p as non-prime
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Print all prime numbers up to n
printf("Prime numbers up to %d:\n", n);
for (int p = 2; p <= n; p++) {
if (prime[p])
printf("%d ", p);
}
printf("\n");
// Free allocated memory
free(prime);
}
// Define main function
int main()
{
// Declare variable to hold maximum number
int n;
// Prompt user to enter the maximum number
printf("Enter the maximum number to find primes: ");
// Read user input
scanf("%d", &n);
// Call SieveOfEratosthenes function with user input
SieveOfEratosthenes(n);
return 0;
}
Output
Enter the maximum number to find primes: 100
Prime numbers up to 100:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Time and Space Complexity
- Time Complexity: The time complexity for this algorithm is O(n log log n). This makes it very efficient when dealing with large datasets.
- Space Complexity: The space requirement is O(n). This means that an array of size n+1 will be needed to hold true or false for every number until n itself included.
Applications of the Sieve of Eratosthenes
It is used in various fields which include:
- When large prime factors are used in Cryptography.
- By algorithms that factorize large integers or are used to perform primality tests.
- For generating keys in public-key encryption systems under network security.
- Mathematical software and scientific computing where prime numbers play a significant role.
Conclusion
The Sieve of Eratosthenes is still considered as one of the most efficient and practical ways to find all prime numbers less than an upper bond. Understanding how these types of algorithms work enables one to see the beauty behind them and appreciate mathematical concepts as powerful tools for solving real-life computing problems.