pythonalgorithmprimes

How to find prime numbers in python


I'm new to Python. I am trying to count the prime numbers in a given range. Some of the answers that developers have shared are like this:

import math
def count_primes(num):
    out = []

    for i in range(3,num,2):
        if all(i%j!=0 for j in range(3,int(math.sqrt(i))+1,2)):
            out.append(i)

    print(out)

I wrote a one like this:

import math
def count_primes(num):
    out = []
    for i in range(3,num,2):
        for j in range(3, int(math.sqrt(i))+1,2):
            if i%j != 0:
                out.append(i)           
        print(out)

but it doesn't work. Could somebody please help me. Appreciated!


Solution

  • Neither of your example count_primes() functions actually counts primes -- they simply print odd primes. Let's implement a working version of your trial division code, not using confusing booleans and a bad algorithm, but rather taking advantage of Python's else clause on for loops:

    def collect_odd_primes(number):
        primes = []
    
        for candidate in range(3, number, 2):
            for divisor in range(3, int(candidate ** 0.5) + 1, 2):
                if candidate % divisor == 0:
                    break
            else:  # no break
                primes.append(candidate)
    
        return primes
    
    print(collect_odd_primes(40))
    

    OUTPUT

    > python3 test.py
    [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    >
    

    As @MarkRansom comments, the Sieve of Eratosthenes is the better way to go. (+1) Now, let's convert our code to count odd primes instead:

    def count_odd_primes(number):
        count = 0
    
        for candidate in range(3, number, 2):
            for divisor in range(3, int(candidate ** 0.5) + 1, 2):
                if candidate % divisor == 0:
                    break
            else:  # no break
                count += 1
    
        return count
    
    print(count_odd_primes(40))
    

    OUTPUT

    > python3 test.py
    11
    >