Prime Factorization Using The Sieve Of Eratosthenes in C++

Filed Under: Java
Prime Factorization Using The Sieve Of Eratosthenes

Today we will learn prime factorization using a Sieve of Eratosthenes. For competitive programming, the problems related to prime factors and prime numbers are very common. If you’re studying a data structures and algorithms course, then also, you should learn this concept. First, we will go through the problem statement, and then, we will move toward the algorithm and the underlying concept. So let’s get started.

Also read: Sieve Of Eratosthenes Using C++

Problem Statement

Given a number as input, find all the prime factors of the given number.

For example,

Number: 20 = 2 x 2 x 5
Prime Factors: 2, 5

Number: 33 = 3 x 11
Prime Factors: 3, 11

Number: 47 = 1 x 47
Prime Factors: 47(Prime numbers only, 1 is not a prime number)

Number: 100 = 2 x 2 x 5 x 5
Prime Factors: 2, 5

Number: 1200 = 2 x 2 x 2 x 2 x 3 x 5 x 5
Prime Factors: 2, 3, 5

Number: 343 = 7 x 7 x 7
Prime Factors: 7

Concept of Prime Factorization

We can solve this problem using multiple different approaches. In this article, we will learn to solve it using the Sieve of Eratosthenes. Sieve of Eratosthenes is astonishingly efficient in terms of time complexity, as it takes only O(Nlog2(log2N)) units of time. This is almost linear time complexity. Below are the steps that we would follow while writing the algorithm.

  • To find the prime factors of a number, we need not iterate over all the numbers in the range i = 2 to i = square_root(N).
  • Instead, first, generate the list of prime numbers up to 1000000, and then start iterating over this list.
  • This approach saves us from many iterations that are of no use.
  • Initialize a vector of integers to store the prime factors.
  • Run a loop in the range i = 2 to i = square_root(N).
    • We are running this for loop up to the square_root(N) only because the greatest prime factor of a number can be its square root.
    • During each iteration, do the following steps,
      • If the number is divisible by the current prime number, divide it number until it’s divisible.
        • And push this prime number in the vector of prime factors.
      • Otherwise, move to the next prime number.
  • Once you are out of this loop, check if the value of N == 1 or not
    • If not, then N is also a prime number, add N to the factors.
  • Display the list and return.

Algorithm for Prime Factorization in C++

void find_prime_factors(vector <int> primes, int N)
{
        // initailize the vector
        vector <int> factors;

        int N_new = N;
        int i = 0;
        int p = primes[0];

        // start the loop
        while(p * p <= N_new)
        {
                if(N % p == 0)
                {
                        factors.push_back(p);

                        while(N % p == 0)
                                N /= p;
                }

                i++;
                p = primes[i];
        }

        // if the number is not 1, then the
        // number itself is a prime number
        if(N != 1)
                factors.push_back(N);

        print_factors(factors);
}
Algorithm 3
Algorithm

Prime Factorization Using Sieve The Of Eratosthenes Program

Let’s now look at the code for prime factorization using the Sieve of Eratosthenes algorithm.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void prime_sieve(vector <bool> &sieve, int N)
{
	// mark address 0 and 1 ans false
	// as these are not primes
	sieve[0] = sieve[1] = false;

	// mark all the even numbers as false
	for(int i = 4; i < N; i += 2)
		sieve[i] = false;

	// now mark the multiples of all
	// the odd numbers as false
	for(int i = 3; i < N; i += 2)
		for(int j = i * i; j < N; j += i)
			sieve[j] = false;
}

void store_primes(vector <int> &primes, vector <bool> sieve)
{
	primes.push_back(2);
	for(int i = 3; i < sieve.size(); i += 2)
		if(sieve[i])
			primes.push_back(i);

	return;
}

void print_factors(vector <int> factors)
{
	cout << "The prime factors of the number are:" << endl;
	for(int ele : factors)
		cout << ele << " ";
	cout << endl;
}

void find_prime_factors(vector <int> primes, int N)
{
	// initailize the vector
	vector <int> factors;

	int N_new = N;
	int i = 0;
	int p = primes[0];
	
	// start the loop
	while(p * p <= N_new)
	{
		if(N % p == 0)
		{
			factors.push_back(p);

			while(N % p == 0)
				N /= p;
		}

		i++;
		p = primes[i];
	}

	// if the number is not 1, then the
	// number itself is a prime number
	if(N != 1)
		factors.push_back(N);

	print_factors(factors);
}

int main()
{
	int M = 1000;
	vector <bool> sieve(M, true);
	prime_sieve(sieve, M);

	vector <int> primes;
	store_primes(primes, sieve);

	cout << "Enter the number" << endl;
	int N;
	cin >> N;

	find_prime_factors(primes, N);

	return 0;
}

Output

Prime Factorization Using Sieve Output
Prime Factorization Using Sieve Output

Conclusion

In this article, we learned to find the prime factors of a number using the Sieve of Eratosthenes. We further discussed that the time complexity of this approach is almost linear. In the end, we coded the algorithm and a C++ program to test it. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ and data structures, you can refer to the following websites.

https://www.journaldev.com/60732/remove-consecutive-duplicates-from-string-cpp

https://www.journaldev.com/61089/euclids-division-lemma-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content