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:

Go to the source code of this file.

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.

Definition in file prime_factorization.cpp.

Function Documentation

main()

int main

(

void

)

Main program

Definition at line 62 of file prime_factorization.cpp.

           {
    int num;
    std::cout << "\t\tComputes the prime factorization\n\n";
    std::cout << "Type in a number: ";
    std::cin >> num;
 
    SieveOfEratosthenes(num);
 
    prime_factorization(num);
 
    // Prime factors with their powers in the given number in new line
    for (auto it : factors) {
        std::cout << it.first << " " << it.second << std::endl;
    }
 
    return 0;
}

prime_factorization()

void prime_factorization

(

int

num

)

Prime factorization of a number

Definition at line 40 of file prime_factorization.cpp.

                                  {
    int number = num;
 
    for (int i = 0; prime_numbers[i] <= num; i++) {
        int count = 0;
 
        // termination condition
        if (number == 1) {
            break;
        }
 
        while (number % prime_numbers[i] == 0) {
            count++;
            number = number / prime_numbers[i];
        }
 
        if (count)
            factors.push_back(std::make_pair(prime_numbers[i], count));
    }
}

SieveOfEratosthenes()

void SieveOfEratosthenes

(

int

N

)

Calculating prime number upto a given range

Definition at line 23 of file prime_factorization.cpp.

                                {
    // initializes the array isprime
    memset(isprime, true, sizeof isprime);
 
    for (int i = 2; i <= N; i++) {
        if (isprime[i]) {
            for (int j = 2 * i; j <= N; j += i) isprime[j] = false;
        }
    }
 
    for (int i = 2; i <= N; i++) {
        if (isprime[i])
            prime_numbers.push_back(i);
    }
}

Variable Documentation

factors

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

list of prime factor-pairs

Definition at line 19 of file prime_factorization.cpp.

isprime

bool isprime[1000006]

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

Definition at line 13 of file prime_factorization.cpp.

prime_numbers

std::vector<int> prime_numbers

list of prime numbers

Definition at line 16 of file prime_factorization.cpp.