Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
prime_factorization.cpp File Reference

Prime factorization of positive integers. More...

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
Include dependency graph for prime_factorization.cpp:

Functions

void SieveOfEratosthenes (int N)
 
void prime_factorization (int num)
 
int main ()
 

Variables

bool isprime [1000006]
 
std::vector< int > prime_numbers
 
std::vector< std::pair< int, int > > factors
 

Detailed Description

Prime factorization of positive integers.

Function Documentation

◆ main()

int main ( void  )

Main program

62  {
63  int num;
64  std::cout << "\t\tComputes the prime factorization\n\n";
65  std::cout << "Type in a number: ";
66  std::cin >> num;
67 
69 
71 
72  // Prime factors with their powers in the given number in new line
73  for (auto it : factors) {
74  std::cout << it.first << " " << it.second << std::endl;
75  }
76 
77  return 0;
78 }
Here is the call graph for this function:

◆ prime_factorization()

void prime_factorization ( int  num)

Prime factorization of a number

40  {
41  int number = num;
42 
43  for (int i = 0; prime_numbers[i] <= num; i++) {
44  int count = 0;
45 
46  // termination condition
47  if (number == 1) {
48  break;
49  }
50 
51  while (number % prime_numbers[i] == 0) {
52  count++;
53  number = number / prime_numbers[i];
54  }
55 
56  if (count)
57  factors.push_back(std::make_pair(prime_numbers[i], count));
58  }
59 }
Here is the call graph for this function:

◆ SieveOfEratosthenes()

void SieveOfEratosthenes ( int  N)

Calculating prime number upto a given range

23  {
24  // initializes the array isprime
25  memset(isprime, true, sizeof isprime);
26 
27  for (int i = 2; i <= N; i++) {
28  if (isprime[i]) {
29  for (int j = 2 * i; j <= N; j += i) isprime[j] = false;
30  }
31  }
32 
33  for (int i = 2; i <= N; i++) {
34  if (isprime[i])
36  }
37 }
Here is the call graph for this function:

Variable Documentation

◆ factors

std::vector<std::pair<int, int> > factors

list of prime factor-pairs

◆ isprime

bool isprime[1000006]

Declaring variables for maintaing prime numbers and to check whether a number is prime or not

◆ prime_numbers

std::vector<int> prime_numbers

list of prime numbers

prime_numbers
std::vector< int > prime_numbers
Definition: prime_factorization.cpp:16
factors
std::vector< std::pair< int, int > > factors
Definition: prime_factorization.cpp:19
std::vector::push_back
T push_back(T... args)
std::cout
SieveOfEratosthenes
void SieveOfEratosthenes(int N)
Definition: prime_factorization.cpp:23
std::endl
T endl(T... args)
prime_factorization
void prime_factorization(int num)
Definition: prime_factorization.cpp:40
std::make_pair
T make_pair(T... args)
std::cin
std::memset
T memset(T... args)
isprime
bool isprime[1000006]
Definition: prime_factorization.cpp:13