wehub-resource-sync
29cfe479ab
Awesome CI Workflow / Code Formatter (push) Waiting to run
Awesome CI Workflow / Compile checks (macOS-latest) (push) Blocked by required conditions
Awesome CI Workflow / Compile checks (ubuntu-latest) (push) Blocked by required conditions
Awesome CI Workflow / Compile checks (windows-latest) (push) Blocked by required conditions
14 lines
734 B
Markdown
14 lines
734 B
Markdown
# 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**
|