Ritobroto Kalita 512efd1861 fix: Update documentations and tests for fibonacci.cpp (#2793)		1 周之前
..
CMakeLists.txt	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
README.md	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
aliquot_sum.cpp	2fd530cba1 [fix/docs]: fit `armstrong_number.cpp` to guidelines (#2457)	1 年之前
approximate_pi.cpp	aaf84ab08f fix: fit `approximate_pi.cpp` to guidelines (#2499)	1 年之前
area.cpp	b957b1dfef feat: Add hemi-sphere area algorithm (#2767)	2 周之前
armstrong_number.cpp	e3f0551f98 [fix/docs]: fit `check_amicable_pair.cpp` to guidelines (#2465)	1 年之前
binary_exponent.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
binomial_calculate.cpp	0b890fd842 feat: add program to calculate binomial coefficients (#1448)	3 年之前
check_amicable_pair.cpp	e3f0551f98 [fix/docs]: fit `check_amicable_pair.cpp` to guidelines (#2465)	1 年之前
check_factorial.cpp	2d492834b1 feat: update CMake version to 3.26.4 (#2486)	1 年之前
check_prime.cpp	2d492834b1 feat: update CMake version to 3.26.4 (#2486)	1 年之前
complex_numbers.cpp	5baf1ad89f formatting source-code for 247301c5b5f1c61c015fd2f852832651dc443c2e	4 年之前
double_factorial.cpp	b1620ff2f5 formatting source-code for e1b1c71e7cca268c9fbad41d2d6b315ff63b9756	4 年之前
eratosthenes.cpp	1d2c5d9d97 feat: add Sieve of Eratosthenes (originally by @thechubbypanda) (#2442)	1 年之前
eulers_totient_function.cpp	4b740d464c fix: fit euler's totient to the contribution guidelines (#2447)	1 年之前
extended_euclid_algorithm.cpp	4a03c62dd3 Fix compilation failure with gcc >= 13 (#2702)	1 月之前
factorial.cpp	37aae7ced4 docs: fit `factorial.cpp` to contribution guidelines (#2487)	1 年之前
fast_power.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
fibonacci.cpp	512efd1861 fix: Update documentations and tests for fibonacci.cpp (#2793)	1 周之前
fibonacci_fast.cpp	4c6b3b86c1 formatting source-code for c7ff9d66f1e7c18b43e51d183f1299b25293ac55	4 年之前
fibonacci_large.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
fibonacci_matrix_exponentiation.cpp	f222acde97 Nth fibonacci number using matrix exponentiation (#1215)	3 年之前
fibonacci_sum.cpp	67e26cfbae feat: Add ncr mod p code (#1325)	3 年之前
finding_number_of_digits_in_a_number.cpp	fddbf08f5a feat: added log code for counting digits (#2234)	1 年之前
gcd_iterative_euclidean.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
gcd_of_n_numbers.cpp	fddedd8864 fix: Adding documentations, tests, and amending algorithm for gcd_of_n_numbers.cpp (#2766)	2 周之前
gcd_recursive_euclidean.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
integral_approximation.cpp	a41b707919 feat: added integral approximation algorithm (#1485)	3 年之前
integral_approximation2.cpp	b3a0070a74 feat: Reworked/updated sorting/selection_sort.cpp. (#1613)	3 年之前
inv_sqrt.cpp	f7d656cb17 feat: Add inverse inverse root functions (#1570)	3 年之前
iterative_factorial.cpp	8a368240e2 fix: remove memory leak `iterative_factorial.cpp` (#2535)	1 月之前
large_factorial.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
large_number.h	8736dce71a make multiplication 64-bit	4 年之前
largest_power.cpp	de99092144 feat: largest_power (#1406)	3 年之前
lcm_sum.cpp	67e26cfbae feat: Add ncr mod p code (#1325)	3 年之前
least_common_multiple.cpp	d58954523f fix: Integer overflow of least_common_multiple. (#970)	4 年之前
linear_recurrence_matrix.cpp	73ff948b0d feat: Solving linear recurrence using Matrix Exponentiation (with examples). (#1463)	3 年之前
magic_number.cpp	806f3251ee Update math/magic_number.cpp	4 年之前
miller_rabin.cpp	bbe1ff1286 formatting source-code for a48d05fb6223cedde57fa487fb79ee51651d5985	4 年之前
modular_division.cpp	a4f830b90b clang-format and clang-tidy fixes for 7293e15a	3 年之前
modular_exponentiation.cpp	fee3a74e35 feat: Add modular_exponentiation.cpp (#1276)	4 年之前
modular_inverse_fermat_little_theorem.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
modular_inverse_simple.cpp	274cab6914 feat: add modular_inverse_simple (#1937)	2 年之前
n_bonacci.cpp	33750ec1f8 fix: cover the cases `n == 0` and `m < n` in `N_bonacci` (#2468)	1 年之前
n_choose_r.cpp	67e26cfbae feat: Add ncr mod p code (#1325)	3 年之前
ncr_modulo_p.cpp	af72fab013 fix: make interface of `NCRModuloP` fail-safe (#2469)	1 月之前
number_of_positive_divisors.cpp	dcf5fa4241 fix, test: simplification and tests for number_of_positive_divisors (#975)	4 年之前
perimeter.cpp	c1a9019d2a feat: add perimeter.cpp (#1897)	2 年之前
power_for_huge_numbers.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
power_of_two.cpp	0f5b36d437 fix: power_of_two algorithm redundant conditional 'else' (#1936)	2 年之前
prime_factorization.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
prime_numbers.cpp	1f6c39bcf2 fix: rewrite prime numbers using linear sieve (#1810)	3 年之前
primes_up_to_billion.cpp	2aec4efdd3 fix: integer overflow due to multiplication fixed (#886)	4 年之前
quadratic_equations_complex_numbers.cpp	a0227012ec feat: add Quadratic equations complex numbers (#2451)	1 年之前
realtime_stats.cpp	0356a9cdf3 fix: Various LGTM fixes	4 年之前
sieve_of_eratosthenes.cpp	42e1246ffc fix, test: Refactor of sieve_of_eratosthenes (#969)	4 年之前
sqrt_double.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
string_fibonacci.cpp	aaa08b0150 Major rework to improve code quality and add automation checks (#805)	4 年之前
sum_of_binomial_coefficient.cpp	67e26cfbae feat: Add ncr mod p code (#1325)	3 年之前
sum_of_digits.cpp	c563fc6694 formatting source-code for 9bc80876e81aeb73c9490417f19cc1d91e60e0d1	4 年之前
vector_cross_product.cpp	f4423503a1 cross product of two vectors (#1292)	3 年之前
volume.cpp	050c99eb0a feat: added math/volume.cpp (#1796)	3 年之前

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

README.md

Prime factorization # {#section}