math Directory Reference

Files
	aliquot_sum.cpp
	Program to return the Aliquot Sum of a number.
	approximate_pi.cpp
	Implementation to calculate an estimate of the number π (Pi).
	area.cpp
	Implementations for the area of various shapes.
	armstrong_number.cpp
	binary_exponent.cpp
	C++ Program to find Binary Exponent Iteratively and Recursively.
	binomial_calculate.cpp
	Program to calculate Binomial coefficients
	check_amicable_pair.cpp
	A C++ Program to check whether a pair of numbers is an amicable pair or not.
	check_factorial.cpp
	A simple program to check if the given number is a factorial of some number or not.
	check_prime.cpp
	A simple program to check if the given number is Prime or not.
	complex_numbers.cpp
	An implementation of Complex Number as Objects.
	double_factorial.cpp
	Compute double factorial: \(n!!\).
	eratosthenes.cpp
	The Sieve of Eratosthenes
	eulers_totient_function.cpp
	Implementation of Euler's Totient @description Euler Totient Function is also known as phi function.
	extended_euclid_algorithm.cpp
	GCD using [extended Euclid's algorithm] (https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)
	factorial.cpp
	Find the factorial of a given number.
	fast_power.cpp
	Faster computation for \(a^b\).
	fibonacci.cpp
	n-th Fibonacci number.
	fibonacci_fast.cpp
	Faster computation of Fibonacci series.
	fibonacci_large.cpp
	Computes N^th Fibonacci number given as input argument. Uses custom build arbitrary integers library to perform additions and other operations.
	fibonacci_matrix_exponentiation.cpp
	This program computes the N^th Fibonacci number in modulo mod input argument .
	fibonacci_sum.cpp
	An algorithm to calculate the sum of Fibonacci Sequence: \(\mathrm{F}(n) + \mathrm{F}(n+1) + .. + \mathrm{F}(m)\).
	finding_number_of_digits_in_a_number.cpp
	[Program to count digits in an integer](https://www.geeksforgeeks.org/program-count-digits-integer-3-different-methods)
	gcd_iterative_euclidean.cpp
	Compute the greatest common denominator of two integers using iterative form of Euclidean algorithm
	gcd_of_n_numbers.cpp
	This program aims at calculating the GCD of n numbers.
	gcd_recursive_euclidean.cpp
	Compute the greatest common denominator of two integers using recursive form of Euclidean algorithm
	integral_approximation.cpp
	Compute integral approximation of the function using Riemann sum
	integral_approximation2.cpp
	Monte Carlo Integration
	inv_sqrt.cpp
	Implementation of the inverse square root Root.
	iterative_factorial.cpp
	Iterative implementation of Factorial
	large_factorial.cpp
	Compute factorial of any arbitratily large number/.
	large_number.h
	Library to perform arithmatic operations on arbitrarily large numbers.
	largest_power.cpp
	Algorithm to find largest x such that p^x divides n! (factorial) using Legendre's Formula.
	lcm_sum.cpp
	An algorithm to calculate the sum of LCM: \(\mathrm{LCM}(1,n) + \mathrm{LCM}(2,n) + \ldots + \mathrm{LCM}(n,n)\).
	least_common_multiple.cpp
	linear_recurrence_matrix.cpp
	magic_number.cpp
	A simple program to check if the given number is a magic number or not. A number is said to be a magic number, if the sum of its digits are calculated till a single digit recursively by adding the sum of the digits after every addition. If the single digit comes out to be 1,then the number is a magic number.
	miller_rabin.cpp
	modular_division.cpp
	An algorithm to divide two numbers under modulo p Modular Division
	modular_exponentiation.cpp
	C++ Program for Modular Exponentiation Iteratively.
	modular_inverse_fermat_little_theorem.cpp
	C++ Program to find the modular inverse using Fermat's Little Theorem
	modular_inverse_simple.cpp
	Simple implementation of modular multiplicative inverse
	n_bonacci.cpp
	Implementation of the N-bonacci series.
	n_choose_r.cpp
	Combinations n choose r function implementation
	ncr_modulo_p.cpp
	This program aims at calculating nCr modulo p.
	number_of_positive_divisors.cpp
	C++ Program to calculate the number of positive divisors.
	perimeter.cpp
	Implementations for the perimeter of various shapes.
	power_for_huge_numbers.cpp
	Compute powers of large numbers.
	power_of_two.cpp
	Implementation to check whether a number is a power of 2 or not.
	prime_factorization.cpp
	Prime factorization of positive integers.
	prime_numbers.cpp
	Get list of prime numbers.
	primes_up_to_billion.cpp
	Compute prime numbers upto 1 billion.
	quadratic_equations_complex_numbers.cpp
	Calculate quadratic equation with complex roots, i.e. b^2 - 4ac < 0.
	realtime_stats.cpp
	Compute statistics for data entered in rreal-time.
	sieve_of_eratosthenes.cpp
	Prime Numbers using Sieve of Eratosthenes
	sqrt_double.cpp
	Calculate the square root of any positive real number in \(O(\log N)\) time, with precision fixed using bisection method of root-finding.
	string_fibonacci.cpp
	This Programme returns the Nth fibonacci as a string.
	sum_of_binomial_coefficient.cpp
	Algorithm to find sum of binomial coefficients of a given positive integer.
	sum_of_digits.cpp
	A C++ Program to find the Sum of Digits of input integer.
	vector_cross_product.cpp
	Calculates the Cross Product and the magnitude of two mathematical 3D vectors.
	volume.cpp
	Implmentations for the volume of various 3D shapes.

Detailed Description

Prime Factorization is a very important and useful technique to factorize any number into its prime factors. It has various applications in the field of number theory.

The method of prime factorization involves two function calls. First: Calculating all the prime number up till a certain range using the standard Sieve of Eratosthenes.

Second: Using the prime numbers to reduce the the given number and thus find all its prime factors.

The complexity of the solution involves approx. O(n logn) in calculating sieve of eratosthenes O(log n) in calculating the prime factors of the number. So in total approx. O(n logn).

Requirements: For compile you need the compiler flag for C++ 11