Table of contents

Introduction

1.1.

Note:

Finding all the prime numbers using sieve

Code to find the prime numbers(C++)

3.1.

Output:

Finding prime numbers in Linear Time Complexity

Code to find prime numbers in Linear-time

5.1.

Output:

5.2.

Time Complexity

5.3.

Space Complexity

Frequently Asked Questions

Key Takeaways

Last Updated: Mar 27, 2024

Sieve of Eratosthenes with Linear time complexity

Q: Explain prime factorization using the sieve of Eratosthenes.

spf[ i ] => smallest prime factor of iwhile (N != 1){print spf[N]N = N / spf[N]}

Q: In this blog, we learned about the sieve of Eratosthenes, to find prime numbers using a sieve, the prime factorization using the sieve of Eratosthenes, and finding prime factors in linear-time with proper concepts, the code of it and its algorithm implementation.

Try problems of the sieve of Eratosthenes here on CodeStudio to understand its working algorithms. To be more confident in competitive programming concepts and data structures and algorithms, try out our Competitive Programming Course.

Author Sneha Mallik

Introduction

Sieve of Eratosthenes is used to print all of the prime numbers in a given range efficiently. It is widely used in the world of competitive programming, where we try to find solutions in a better-optimized way.

Sieve of Eratosthenes is an ancient algorithm of 200+ years old, which is a simple and elegant method to find primes that are less than or equal to ‘N’ where ‘N’ is the upper range to be taken as input.

Note:

A prime number has two factors: 1 and the number itself.
0 and 1 are not prime numbers.

Read more about segmented sieve and try out problems here.

Finding all the prime numbers using sieve

Let us assume that we have numbers from 1 to 50.

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

Since 1 is neither composite nor prime, we will exclude 1 from the table where we have to find all the prime between the range [1, 50].

Now, we will mark all the multiples of 2 as below.

2² = 4. Hence, we will mark from 4 onwards.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

Now, we will move forward to mark all the multiples of 3.

3² = 9. Hence, we will mark from 9 onwards.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

Now, we will move forward, and here we notice that ‘4’ is marked. Hence, we move again to the next number to mark all the multiples of 5.

5² = 25. Hence, we will mark from 25 onwards.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

Now, we will move forward, and here we notice that ‘6’ is marked. Hence, we move again to the next number to mark all the multiples of 7.

7² = 49. Hence, we will mark from 49 onwards.

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

Now moving on to the next number, ‘8’ is marked and its square is 64, which is more than our given range, we will stop working in the loop here. By doing this whole process, we eliminated all the non-prime numbers to get only the prime numbers.

The prime no.s are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Code to find the prime numbers(C++)

// Code to find all the prime numbers using sieve
#include <iostream>
using namespace std;

void primeSieveNumber(int N){

  // Taking an array size of 100
  int prime[100] = {0};
  for(int i = 2; i * i <= N; i++){
  if(prime[i] == 0){
  for(int j = i * i; j <= N; j += i){
prime[j] = 1;
}
}
}

  // For printing out prime no.s
  cout << "The prime numbers from 1 to " << N << " are: ";
  for(int i = 2; i <= N; i++){
  if(prime[i] == 0){
  cout << i << " ";
}
}
  cout << endl;
}

int main(){

  // Take an input N to find prime numbers from 1 to N
  int N;
  cout << "Enter a number 'N' to find prime no.s from [1-N]: ";
  cin >> N;
primeSieveNumber(N);
  return 0;
}

Output:

Enter a number 'N' to find prime no.s from [1-N]: 14
The prime no.s from 1 to 14 are: 2 3 5 7 11 13

Time Complexity - O(N (log(log N)) where ‘N’ is the upper bound of the input.

{(N / 2) + (N / 3) + (N / 5) + (N / 7) + … + (N / P)},

where ‘P’ is the highest prime number, ‘P’ <= ‘N’

=> N {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)}

where {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)}

is the harmonic progression of sum of primes

=> N (log (log N))

as {(1 / 2) + (1 / 3) + (1 / 5) + (1 / 7) + … + (1 / P)} = log(log(N))

=> O(N log log N) time complexity

Space Complexity - O(N) where ‘N’ is the upper bound of the input.

To find out the prime numbers from 1 to ‘N’, the space complexity is O(N) since we are creating an array of size ‘N’. It also means that if ‘N’ is constant, then the space complexity is O(1).

Let us optimize the above code to get a linear time complexity.

Finding prime numbers in Linear Time Complexity

There is a given upper range, ‘N’ till which we have to find prime numbers.

First, we will check for each number if it is prime where ‘I’ lies in the range [2, N - 1].
While iterating, for every prime number ‘j’ less than or equal to the smallest prime factor ‘spf’ of ‘i’, we will mark all the numbers ‘i’ * ‘spf’ as composite/not_prime.
We will mark the smallest prime factor of ‘i’ * ‘spf’ as ‘j’.

Code to find prime numbers in Linear-time

/*
Code to find smallest prime factors using a sieve in linear-time
complexity
*/
#include <iostream>
#include <vector>

#include <climits>
using namespace std;

const long long M = 10000000;

// If the number is prime, 'isPrime' is true.
vector<long long> isPrime(M, true);

// 'prime' holds all the prime numbers till N
vector<long long> primeNo;

// 'spf' stores the smallest prime factors of N
vector<long long> spf(M);

void modifiedSieve(int N){

  // We will mark '0' and '1' as false since they are not prime
isPrime[0] = isPrime[1] = false;

  for (long long int i = 2; i < N; i++){
  if (isPrime[i] == true){
primeNo.push_back(i);

  // Prime no. is its own smallest prime factor
spf[i] = i;
}

  // Removing all multiples of i * primeNo[j]
  for (long long int j = 0; j < (int)primeNo.size() &&
i * primeNo[j] < N && primeNo[j] <= spf[i]; j++){
isPrime[i * primeNo[j]] = false;
spf[i * primeNo[j]] = primeNo[j];
}
}

  // For printing out the smallest prime factors
  cout << "The smallest prime factors from 1 to " << N << " are: ";
  for (int i = 0; i < primeNo.size() && primeNo[i] <= N; i++){
  cout << primeNo[i] << " ";
}
}

int main(){

  // Take an input 'N' to find prime factors from 1 to N
  int N;
  cout << "Enter a number 'N' to find prime no.s from [1-N]: ";
  cin >> N;
modifiedSieve(N);
  return 0;
}

Output:

Enter a number 'N' to find prime no.s from [1-N]: 20
The smallest prime factors from 1 to 20 are: 2 3 5 7 11 13 17 19

Time Complexity

The modified sieve of Eratosthenes has a time complexity of O(N) as we cross each number at most once when we are setting its smallest prime factor. Once all the non-prime numbers are marked as false, number P * N (where ‘P’ is the smallest prime factor and N is the number) will be marked as false when we look at ‘N’.

Space Complexity

The space complexity is O(N) as we create an array of size ‘N’ that will take O(N) space. Therefore, overall space complexity will be O(N)

Frequently Asked Questions

Explain prime factorization using the sieve of Eratosthenes.

spf[ i ] => smallest prime factor of i

while (N != 1){

print spf[N]

N = N / spf[N]

}

Sieve of Eratosthenes is used to make the code run faster. Here, we will be dividing a number ‘N’ with its spf(smallest prime factor) till it reaches 1.

For example:

We take a number, ‘N’ = 30.

The smallest prime factor of 30 is 2.

Dividing ‘N’ with 2:

30 / 2 = 15

Now, dividing 15 with its spf 3:

15 / 3 = 5

Now, dividing 5 with its spf 5:

5 / 5 = 1

Therefore, the prime factors of 30 include 2, 3 and 5.

2. What are the advantages of using the sieve of Eratosthenes?

It is an optimized and efficient algorithm for finding out the prime numbers in a particular range.
It has low implementation.

3. What is meant by sieve?

Sieve is defined as the way or device used for filtering out wanted from unwanted materials. For example, we find out the prime numbers in a set of numbers and leave out the composite numbers.

Key Takeaways

In this blog, we learned about the sieve of Eratosthenes, to find prime numbers using a sieve, the prime factorization using the sieve of Eratosthenes, and finding prime factors in linear-time with proper concepts, the code of it and its algorithm implementation.

Try problems of the sieve of Eratosthenes here on Coding Ninjas Studio to understand its working algorithms. To be more confident in competitive programming concepts and data structures and algorithms, try out our Competitive Programming Course.

Credits: GIPHY

Happy Learning!

By Sneha Mallik

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50

	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50