Skip to content

Latest commit

 

History

History
 
 

math

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
CMakeLists.txt
CMakeLists.txt
 
 
README.md
README.md
 
 
approximate_pi.cpp
approximate_pi.cpp
 
 
area.cpp
area.cpp
 
 
armstrong_number.cpp
armstrong_number.cpp
 
 
binary_exponent.cpp
binary_exponent.cpp
 
 
binomial_calculate.cpp
binomial_calculate.cpp
 
 
check_amicable_pair.cpp
check_amicable_pair.cpp
 
 
check_factorial.cpp
check_factorial.cpp
 
 
check_prime.cpp
check_prime.cpp
 
 
complex_numbers.cpp
complex_numbers.cpp
 
 
double_factorial.cpp
double_factorial.cpp
 
 
eulers_totient_function.cpp
eulers_totient_function.cpp
 
 
extended_euclid_algorithm.cpp
extended_euclid_algorithm.cpp
 
 
factorial.cpp
factorial.cpp
 
 
fast_power.cpp
fast_power.cpp
 
 
fibonacci.cpp
fibonacci.cpp
 
 
fibonacci_fast.cpp
fibonacci_fast.cpp
 
 
fibonacci_large.cpp
fibonacci_large.cpp
 
 
fibonacci_matrix_exponentiation.cpp
fibonacci_matrix_exponentiation.cpp
 
 
fibonacci_sum.cpp
fibonacci_sum.cpp
 
 
finding_number_of_digits_in_a_number.cpp
finding_number_of_digits_in_a_number.cpp
 
 
gcd_iterative_euclidean.cpp
gcd_iterative_euclidean.cpp
 
 
gcd_of_n_numbers.cpp
gcd_of_n_numbers.cpp
 
 
gcd_recursive_euclidean.cpp
gcd_recursive_euclidean.cpp
 
 
integral_approximation.cpp
integral_approximation.cpp
 
 
integral_approximation2.cpp
integral_approximation2.cpp
 
 
inv_sqrt.cpp
inv_sqrt.cpp
 
 
large_factorial.cpp
large_factorial.cpp
 
 
large_number.h
large_number.h
 
 
largest_power.cpp
largest_power.cpp
 
 
lcm_sum.cpp
lcm_sum.cpp
 
 
least_common_multiple.cpp
least_common_multiple.cpp
 
 
linear_recurrence_matrix.cpp
linear_recurrence_matrix.cpp
 
 
magic_number.cpp
magic_number.cpp
 
 
miller_rabin.cpp
miller_rabin.cpp
 
 
modular_division.cpp
modular_division.cpp
 
 
modular_exponentiation.cpp
modular_exponentiation.cpp
 
 
modular_inverse_fermat_little_theorem.cpp
modular_inverse_fermat_little_theorem.cpp
 
 
n_bonacci.cpp
n_bonacci.cpp
 
 
n_choose_r.cpp
n_choose_r.cpp
 
 
ncr_modulo_p.cpp
ncr_modulo_p.cpp
 
 
number_of_positive_divisors.cpp
number_of_positive_divisors.cpp
 
 
perimeter.cpp
perimeter.cpp
 
 
power_for_huge_numbers.cpp
power_for_huge_numbers.cpp
 
 
power_of_two.cpp
power_of_two.cpp
 
 
prime_factorization.cpp
prime_factorization.cpp
 
 
prime_numbers.cpp
prime_numbers.cpp
 
 
primes_up_to_billion.cpp
primes_up_to_billion.cpp
 
 
realtime_stats.cpp
realtime_stats.cpp
 
 
sieve_of_eratosthenes.cpp
sieve_of_eratosthenes.cpp
 
 
sqrt_double.cpp
sqrt_double.cpp
 
 
string_fibonacci.cpp
string_fibonacci.cpp
 
 
sum_of_binomial_coefficient.cpp
sum_of_binomial_coefficient.cpp
 
 
sum_of_digits.cpp
sum_of_digits.cpp
 
 
vector_cross_product.cpp
vector_cross_product.cpp
 
 
volume.cpp
volume.cpp
 
 

README.md

Prime factorization # {#section}

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