Prime Factorization Using The Sieve Of Eratosthenes in C++
source link: https://www.journaldev.com/61222/prime-factorization-sieve-of-eratosthenes-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Prime Factorization Using The Sieve Of Eratosthenes in C++
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 5Prime Factors: 2, 5Number: 33 = 3 x 11Prime Factors: 3, 11Number: 47 = 1 x 47Prime Factors: 47(Prime numbers only, 1 is not a prime number)Number: 100 = 2 x 2 x 5 x 5Prime Factors: 2, 5Number: 1200 = 2 x 2 x 2 x 2 x 3 x 5 x 5Prime Factors: 2, 3, 5Number: 343 = 7 x 7 x 7Prime Factors: 7Concept 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.
- If the number is divisible by the current prime number, divide it number until it’s divisible.
- 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 vectorvector <int> factors;int N_new = N;int i = 0;int p = primes[0];// start the loopwhile(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 numberif(N != 1)factors.push_back(N);print_factors(factors);}
AlgorithmPrime 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 primessieve[0] = sieve[1] = false;// mark all the even numbers as falsefor(int i = 4; i < N; i += 2)sieve[i] = false;// now mark the multiples of all// the odd numbers as falsefor(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 vectorvector <int> factors;int N_new = N;int i = 0;int p = primes[0];// start the loopwhile(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 numberif(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 OutputConclusion
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
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK