# What is the most efficient way to find prime factors of a number (python)?

Updated: Dec 31, 2018

__One of the best method is to use Sieve of Eratosthenes__

`Create a list of prime flags with their indices representing corresponding numbers.`

`0 → `**False**

`1 → `**False**

`2 → `**True**

**and** so on..

Flag → **False** for each multiples of index if it’s **prime**.

Python program is shown below,

**def** primes(n):

` flag = [`**True**] * n

` flag[0] = flag[1] = `**False**

` `**for** (index, prime) **in** enumerate(flag):

` `**if** prime:

` `**yield** index

` `**for** i **in** range(index*index, n, index):

` flag[i] = `**False**

Print the last item from generator,

`p = `**None**

**for** p **in** is_prime(1000000):

` `**pass**

**print**(p)

`>>> 999983`

__Regular way__

To make the program efficient you need to:

Cross out 1 as it's not prime.

Cross out all of the multiples of 2 if input number is odd.

Cross out all of the multiples of 3 if input number is even.

Most importantly, for number N, you only need to test until you get to a prime till √N.

If a number N has a prime factor larger than √N , then it surely has a prime factor smaller than √N. So it's sufficient to search for prime factors in the range [1,√N]. If no prime factors exist in the range [1,√N], then N itself is prime and there is no need to continue searching beyond that range.

You can do it like this,

**def** is_prime(num):

` `**if** num<2:

` `**return** **False**

` `**else**:

` `**return** **all**(num%i **for** i **in** **range**(2, **int**(num ** 0.5)+1))

Checking if 1471 is prime,

`is_prime(1471)`

**True**

Let's say you want to check all the prime numbers up-to 2 million,

`prime_list = [i `**for** i **in** range(2000000) **if** is_prime(i)]

I have seen similar type of problems in project Euler like sum of primes or total number of primes below (a very large number). If the number is small you can simply divide by all the numbers till (n-1) and check if it’s prime or not, but that program (shown below) performs very bad if the number is big.

**def** is_prime(num):

** ****if** num < 2:

` `**return** **False**

` `**for** i **in** range(2, num):

` `**if** num%i==0:

` `**return** **False**

** ****else**:

` `**return** **True**

`For example: is_prime(47)`

**True**

`>>> %timeit ("is_prime(47)")`

`10.9 ns ± 0.0779 ns per loop (mean ± std. dev. of 7 runs, 100000000 loops each)`

Above program performs very bad if the number is big. Better solution is, instead of dividing by all the numbers up-to (n-1), you just need to check if number is divisible till sqrt(num).

**def** is_prime(x):

` '''Checking if number is prime, run until sqrt(number)'''`

` sqrt = round(x ** 0.5) `

` `**if** x < 2:

` `**return** **False**

` `**else**:

` `**for** i **in** range(2, sqrt + 1):

` `**if** x%i == 0:

` `**return** **False**

` `**else**:

` `**return** **True**

`OR,`

` `**def** is_prime(num):

` `**if** num<2:

` `**return** **False**

` `**else**:

` `**return** **all**(num%i **for** i **in** **range**(2, **int**(num ** 0.5)+1))

That’s it, now use list comprehension to get prime_list and print whatever you need.

`>>> prime_list=[i `**for** i **in** range(3000000) **if** is_prime(i)]

`>>> `**print**(f"Number of primes below 3 million: {**len**(prime_list)}")

`>>> `**print**(f"Sum of primes below 3 million: {**sum**(prime_list)}")

`>>> `**print**(prime_list)

`Number of primes below 3 million: 216816 `

`Sum of primes below 3 million: 312471072265 `

`[2, 3, 5, 7, 11, 13, 17, 19....... ]`