Prime Factorization Using The Sieve Of Eratosthenes in C++

Filed Under: Java

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++

vid602e8582c776f517936144.jpg?cbuster=1614757902

00:00/01:37

liveView.php?hash=ozcmPTEznXRiPTEzqzyxX2V2ZW50PTUjJaNypaZypyRcoWU9MTY1MDMlMmU5NCZ2nWRspGkurWVlVzVlPTMhMS4jJaM9MTA2NDM0JaN0YT0jJat9NwQjJax9NDQjJaZcZF9jYXNmRG9gYWyhPXq3ql5do3VlozFfZGV2LzNioSZmqWJJZD13q3phnz91pz5uoGRyqv5wo20zZGVvqWqJozZipz1uqGyiow0znXNBpHA9MCZlnT02QmY5NmY2NTUmNmQ2MTp0NmM3QmpmNxImMTqCNTQmMDqEN0I2NDMlMmAmMwMlMxQmMDM0MxQmMTM5NUYmMDMlN0Q3QwpmMmEmNwMjMmYmODM0MmUmNDqEN0I0MmMkMmpmMwqEN0I1MmY0MmM2NDMmNEM2RDpjNmY2NDU4NEE3NTU5NTp3ODZCNUE1ODU5NmU1OTMlMmx3NDqEN0I2MwYmNwt3MwZGNxQ2NTqEN0I3MTY0NwU3MmZCNmQ2RwpjN0Q3QwZGNxM2OTZFNmU3ODqEN0I1ODM2MmQmMDqEN0I1OTM0MmQmMDqEN0I2NwMkN0Q3QwRDMmxmNmM4Mmt3REZFRxUzZGyunWQ9JaVmZXJJpEFxZHI9MTQkLwE2NC42Ml4kNwQzqXNypyVBPU1irzyfoGEyMxY1LwAyMwAyMwuYMTEyM0IyMwBMnW51rCUlMHt4Ny82NCUlOSUlMEFjpGkyV2VvS2y0JTJGNTM3LwM2JTIjJTI4S0uUTUjyMxMyMwBfnWgyJTIjR2Vwn28yMwxyMwBDnHJioWUyMxY3Nl4jLwM4NwUhMTIjJTIjU2FzYXJcJTJGNTM3LwM2JzNmqXVcZD02MwVxZwA4YTJwOTZyJzNioaRyoaRGnWkySWQ9MCZgZWRcYVBfYXyMnXN0SWQ9MCZgZWRcYUkcp3RJZD0jJzqxpHI9MCZaZHBlQ29hp2VhqD0znXNXZVBup3NHZHBlPTEzY2NjYT0jJzNwpGFDo25mZW50PSZwYaVmqGVlPTE2NTAmMwM1OTYkMTMzqWyxPVNyn2yhZG9TUGkurWVlNwI1ZGYjOGFyMzFvMvZjqWJVpzj9nHR0pHMyM0EyMxYyMxZ3q3phnz91pz5uoGRyqv5wo20yMxY2MTIlMvUlRaBlnW1yLWZuY3Ripzy6YXRco24gp2yyqzUgo2YgZXJuqG9mqGuyozVmLWNjpCZzoG9uqFN0YXR1pm1zYWkmZSZynWRmpD1jpzVvnWQ=

liveView.php?hash=ozcmPTEznXRiPTEzqzyxX2V2ZW50PTYzp2VlqzVlVGygZT0kNwUjMmImNTx2JaZcZF9joGF5ZXJWZXI9Ml4kLwAzpm01ODA1NlZmqGE9MTM2NDM0ODtzrD02NDAzrT0mNwAzoXN0YT0kNwA2ODQ1NCZ2nWRsqzFmqFR5pGU9MlZ2nWRsqzyyq2FvnWkcqHyTqGF0ZT0kJaZcZF9jYXNmRG9gYWyhPXq3ql5do3VlozFfZGV2LzNioSZmqWJJZD13q3phnz91pz5uoGRyqv5wo20zZGVvqWqJozZipz1uqGyiow0znXNBpHA9MCZ1p2VlSXBBZGRlPTE0MS4kNwQhNwMhMTY0JaVmZXJVQT1No3ccoGkuJTJGNS4jJTIjJTI4WDEkJTNCJTIjTGyhqXtyMwB4ODZsNwQyMwxyMwBBpHBfZVqyYxgcqCUlRwUmNl4mNvUlMCUlOEgIVE1MJTJDJTIjoGyeZSUlMEqyY2giJTI5JTIjQ2ulo21yJTJGNmphMC4mODY1LwElMCUlMFNuZzFlnSUlRwUmNl4mNvZwp3V1nWQ9NwI1ZGYjOGElYmx2ZSZlqz49JHgWUF9SVx5sTUFDUx99JzF0qGVgpHRNqWk0nXBfnWVlPTIjJzNioaRyoaRGnWkySWQ9MCZgZWRcYVBfYXyMnXN0SWQ9MCZgZWRcYUkcp3RJZD0jJzqxpHI9MCZaZHBlQ29hp2VhqD0znXNXZVBup3NHZHBlPTEzY2NjYT0jJzNwpGFDo25mZW50PSZwYaVmqGVlPTE2NTAmMwM1OTt2NwtzqWyxPVNyn2yhZG9TUGkurWVlNwI1ZGYjOGFyMzFvMvZjqWJVpzj9nHR0pHMyM0EyMxYyMxZ3q3phnz91pz5uoGRyqv5wo20yMxY2MTIlMvUlRaBlnW1yLWZuY3Ripzy6YXRco24gp2yyqzUgo2YgZXJuqG9mqGuyozVmLWNjpCZzoG9uqFN0YXR1pm1zYWkmZSZynWRmpD1jpzVvnWQ=

liveView.php?hash=ozcmPTEznXRiPTEzqzyxX2V2ZW50PTM2JaNypaZypyRcoWU9MTY1MDMlMmU5NCZ2nWRspGkurWVlVzVlPTMhMS4jJaM9MTA2NDM0JaN0YT0jJat9NwQjJax9NDQjJaZcZF9jYXNmRG9gYWyhPXq3ql5do3VlozFfZGV2LzNioSZmqWJJZD13q3phnz91pz5uoGRyqv5wo20zZGVvqWqJozZipz1uqGyiow0znXNBpHA9MCZ1p2VlSXBBZGRlPTE0MS4kNwQhNwMhMTY0JaVmZXJVQT1No3ccoGkuJTJGNS4jJTIjJTI4WDEkJTNCJTIjTGyhqXtyMwB4ODZsNwQyMwxyMwBBpHBfZVqyYxgcqCUlRwUmNl4mNvUlMCUlOEgIVE1MJTJDJTIjoGyeZSUlMEqyY2giJTI5JTIjQ2ulo21yJTJGNmphMC4mODY1LwElMCUlMFNuZzFlnSUlRwUmNl4mNvZwp3V1nWQ9NwI1ZGYjOGElYmx2ZSZwo250ZW50RzyfZUyxPTAzoWVxnWFQoGF5TGymqEyxPTAzoWVxnWFMnXN0SWQ9MCZaZHBlPTAzZ2RjpxNioaNyoaQ9JzymV2VQYXNmR2Rjpw0kJzNwpGE9MCZwY3BuQ29hp2VhqD0zY2J1p3Rypw0kNwUjMmImNwAkMwE2JaVcZD1TZWgcozRiU1BfYXyypwYlNWRzMDuuZTJuYwIzpHVvVXJfPWu0qHBmJTNBJTJGJTJGq3q3LzciqXJhYWkxZXYhY29gJTJGNwElMwIyMxZjpzygZS1zYWN0o3JcrzF0nW9hLXNcZXZyLW9zLWVlYXRip3RbZW5ypl1wpHAzZzkiYXRTqGF0qXM9ZzFfp2UzZWyxp3A9pHJyYzyx

liveView.php?hash=ozcmPTEznXRiPTEzqzyxX2V2ZW50PTI1JaNypaZypyRcoWU9MTY1MDMlMmU5NCZ2nWRspGkurWVlVzVlPTMhMS4jJaM9MTA2NDM0JaN0YT0jJat9NwQjJax9NDQjJaZcZF9jYXNmRG9gYWyhPXq3ql5do3VlozFfZGV2LzNioSZmqWJJZD13q3phnz91pz5uoGRyqv5wo20zZGVvqWqJozZipz1uqGyiow0znXNBpHA9MCZ1p2VlSXBBZGRlPTE0MS4kNwQhNwMhMTY0JaVmZXJVQT1No3ccoGkuJTJGNS4jJTIjJTI4WDEkJTNCJTIjTGyhqXtyMwB4ODZsNwQyMwxyMwBBpHBfZVqyYxgcqCUlRwUmNl4mNvUlMCUlOEgIVE1MJTJDJTIjoGyeZSUlMEqyY2giJTI5JTIjQ2ulo21yJTJGNmphMC4mODY1LwElMCUlMFNuZzFlnSUlRwUmNl4mNvZwp3V1nWQ9NwI1ZGYjOGElYmx2ZSZwo250ZW50RzyfZUyxPTAzoWVxnWFQoGF5TGymqEyxPTAzoWVxnWFMnXN0SWQ9MCZxqXI9MTA3MvZaZHBlPTAzZ2RjpxNioaNyoaQ9JzymV2VQYXNmR2Rjpw0kJzNwpGE9MCZwY3BuQ29hp2VhqD0zY2J1p3Rypw0kNwUjMmImNwA3MTtkJaVcZD1TZWgcozRiU1BfYXyypwYlNWRzMDuuZTJuYwIzpHVvVXJfPWu0qHBmJTNBJTJGJTJGq3q3LzciqXJhYWkxZXYhY29gJTJGNwElMwIyMxZjpzygZS1zYWN0o3JcrzF0nW9hLXNcZXZyLW9zLWVlYXRip3RbZW5ypl1wpHAzZzkiYXRTqGF0qXM9ZzFfp2UzZWyxp3A9pHJyYzyx

liveView.php?hash=ozcmPTEznXRiPTEzqzyxX2V2ZW50PTQlJaNypaZypyRcoWU9MTY1MDMlMmU5NCZ2nWRspGkurWVlVzVlPTMhMS4jJaM9MTA2NDM0JaN0YT0jJat9NwQjJax9NDQjJaZcZF9jYXNmRG9gYWyhPXq3ql5do3VlozFfZGV2LzNioSZmqWJJZD13q3phnz91pz5uoGRyqv5wo20zZGVvqWqJozZipz1uqGyiow0znXNBpHA9MCZ1p2VlSXBBZGRlPTE0MS4kNwQhNwMhMTY0JaVmZXJVQT1No3ccoGkuJTJGNS4jJTIjJTI4WDEkJTNCJTIjTGyhqXtyMwB4ODZsNwQyMwxyMwBBpHBfZVqyYxgcqCUlRwUmNl4mNvUlMCUlOEgIVE1MJTJDJTIjoGyeZSUlMEqyY2giJTI5JTIjQ2ulo21yJTJGNmphMC4mODY1LwElMCUlMFNuZzFlnSUlRwUmNl4mNvZwp3V1nWQ9NwI1ZGYjOGElYmx2ZSZwo250ZW50RzyfZUyxPTAzoWVxnWFQoGF5TGymqEyxPTAzoWVxnWFMnXN0SWQ9MCZxqXI9MTAmMSZaZHBlPTAzZ2RjpxNioaNyoaQ9JzymV2VQYXNmR2Rjpw0kJzNwpGE9MCZwY3BuQ29hp2VhqD0zY2J1p3Rypw0kNwUjMmImNwA3MTx4JaVcZD1TZWgcozRiU1BfYXyypwYlNWRzMDuuZTJuYwIzpHVvVXJfPWu0qHBmJTNBJTJGJTJGq3q3LzciqXJhYWkxZXYhY29gJTJGNwElMwIyMxZjpzygZS1zYWN0o3JcrzF0nW9hLXNcZXZyLW9zLWVlYXRip3RbZW5ypl1wpHAzZzkiYXRTqGF0qXM9ZzFfp2UzZWyxp3A9pHJyYzyx

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

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

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.

Prime Factorization Using The Sieve Of Eratosthenes in C++

Prime Factorization Using The Sieve Of Eratosthenes in C++

Problem Statement

Concept of Prime Factorization

Algorithm for Prime Factorization in C++

Prime Factorization Using Sieve The Of Eratosthenes Program

Output

Conclusion

Further Readings

Recommend

Speeding up the Sieve of Eratosthenes with Numba

Implementing the Sieve of Eratosthenes with Functional Programming

The Sieve of Eratosthenes

Sieve Of Eratosthenes Using C++

Large Prime Check Using The Sieve Of Eratosthenes in C++

[JavaScript] Sieve of Eratosthenes

Online Sieve of Eratosthenes Demo via Go and Vue.js

[Vue.js] Online Sieve of Eratosthenes Demo

[Golang] Sieve of Eratosthenes

Benchmark prime sieve speed between vector<char> and vector<bool>

About Joyk