CODEWITHSUNDEEP
pythonalgorithmprimes
1d12d
1d12d

Reputation: 41

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!

Upvotes: 2

Views: 1166

Answers (7)

Hermann12
Hermann12

Reputation: 3415

Prime could be found also with list comprehensive:

val = 30
prime = [x for x in range(2, val) if all(x % y != 0 for y in range(2, x))]

print(prime)
print(len(prime))

Upvotes: 0

Jaden Taylor
Jaden Taylor

Reputation: 13

Here's a way without using import math. If someone can find a faster compile time, I'd like to know. Sincerely, Jaden Taylor

def count_primes(num): 
    primes = [2]
    for i in range(3, num + 1, 2): #iterating through every odd number makes compile time faster
        for j in primes:
            if i % j == 0:
                break
        else:
            primes.append(i)
    return "prime numbers: \n {}".format(primes)

Upvotes: 0

quasireal
quasireal

Reputation: 1

Depending on what program you're running for your code-writing, an alternative method—as opposed to the other answers to this question—would be to write:

    n = int(input("Write an integer:"))
    m = 2

    if n == 1:
        print(n, "is a prime number!")

    if n == 2:
        print(n, "is not a prime number.")

    while n > m:
        if n % m == 0:
            m = m + 1
            print(n, "is not a prime number.")
            break

        if n > n % m > 0:
            m = m + 1
            print(n, "is a prime number!")
            break

It may not be the most efficient, but it gives you a really nice, straight answer to whether or not "x" is a prime number!

Upvotes: 0

cdlane
cdlane

Reputation: 41872

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
>

Upvotes: 2

Red
Red

Reputation: 27557

The reason your code and the other is is different is because their use of the all() method. Have a look at how i implemented the method using bools:

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

    print(out)
    
count_primes(20)

Output:

[3, 5, 7, 11, 13, 17, 19]

Upvotes: 1

Dorian
Dorian

Reputation: 1488

You’re appending to the result of the module is unequal to zero. However, it’s only a prime number if all modulo are unequal to zero (there is an all statement missing in your code).

Upvotes: 0

KetZoomer
KetZoomer

Reputation: 2914

Something like this should work. You have to set a variable, because 15%9 != 0, outputs True.

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

Upvotes: 1

Related Questions