top of page
BlogPageTop

Trending

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

Updated: Feb 9, 2023


One of the best method is to use Sieve of Eratosthenes


0 → False
1 → False
2 → True 
and so on..

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:

  1. Cross out 1 as it's not prime.

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

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

  4. 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....... ]

Comments


Want to share your thoughts about this blog?

Disclaimer: Please note that the information provided on this website is for general informational purposes only and should not be taken as legal advice. Dataneb is a platform for individuals to share their personal experiences with visa and immigration processes, and their views and opinions may not necessarily reflect those of the website owners or administrators. While we strive to keep the information up-to-date and accurate, we make no representations or warranties of any kind, express or implied, about the completeness, accuracy, reliability, suitability, or availability with respect to the website or the information, products, services, or related graphics contained on the website for any purpose. Any reliance you place on such information is therefore strictly at your own risk. We strongly advise that you consult with a qualified immigration attorney or official government agencies for any specific questions or concerns related to your individual situation. We are not responsible for any losses, damages, or legal disputes arising from the use of information provided on this website. By using this website, you acknowledge and agree to the above disclaimer and Google's Terms of Use (https://policies.google.com/terms) and Privacy Policy (https://policies.google.com/privacy).

bottom of page