How do you calculate the amount of prime numbers less than or equal to N?

Question

I want to write a program that determines the amount of prime numbers less than or equal to N (variable containing user input). This is what I've got:

N = int(input("Enter number: "))
count = 0
primes = []
for i in range(2, N+1):
    for j in range(2, int(i/2)+1):
        if (i % j) != 0:
            primes += [i]
            count += 1

print(count)
print(primes)

But when I run the code, it doesn't take the numbers 2 and 3 to be prime. How can I fix this program?

Does this answer your question? [Primality test in python](https://stackoverflow.com/questions/8019343/primality-test-in-python) — Paul Hankin, Mar 18 '23 at 08:58
When I was a math student I remember we had an entire math class lasting a whole semester, whose purpose was to answer this question. — Stef, Mar 18 '23 at 09:12
If you have a given upper bound like this, a more efficient method of prime-gathering is the Sieve of Eratosthenes. See https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. — DWe1, Mar 18 '23 at 09:18
An efficient implementation: [Feasible implementation of a prime-counting function?](https://stackoverflow.com/questions/19070911/feasible-implementation-of-a-prime-counting-function) — Stef, Mar 18 '23 at 09:19
Also if you have sympy: `from sympy import primepi` ([documentation](https://docs.sympy.org/latest/modules/ntheory.html#sympy.ntheory.generate.primepi)) — Stef, Mar 18 '23 at 09:22
Your only problem is it does not include 2 and 3? Solution: add 2 and 3 to the result. Where is the problem? — zvone, Mar 18 '23 at 10:38

astasiak · Accepted Answer · 2023-03-18T08:53:16.397

You can try these changes:

N = int(input("Enter number: "))
count = 0
primes = []
for i in range(2, N+1):
    is_prime = True
    for j in range(2, int(i/2)+1):
        if (i % j) == 0:
            is_prime = False
    if is_prime:
        primes += [i]
        count += 1
print(count)
print(primes)

To check if the number is prime, you need it to check if for ALL smaller numbers the remainder is different than 0.

Also, primes += [i] should be in external loop as you want to count every number at most once.

Note that this solution is far from optimal in terms of efficiency. Some improvements may be:

iterate j only up to math.sqrt(i)+1
break the inner loop as soon as you find the number is not prime
use Sieve of Eratosthenes

Dinux · Answer 2 · 2023-03-18T09:17:31.280

You can try the following code:

primes = []
#Check if given number is prime
def num_is_prime(n):
    if n <= 1 :
        return False
  
    for i in range(2, n):
        if n % i == 0:
            return False
  
    return True
  
#Print prime number less than given number
def print_prime_num(n):
    for i in range(2, n + 1):
        if num_is_prime(i):
            primes.append(i)
            print(i)

    print("Number of prime numbers less than or equal to {} is {}.".format(n,len(primes)))

Then call the function:

print_prime_num(YOUR_NUM)

The 'num_is_prime' function returns true if the given number is prime and false otherwise. Then we print the prime numbers from 2(first prime number) till the given number and add them to a list in the 'print_prime_num' function. We also print the length of list containing the prime numbers.

DarkKnight · Answer 3 · 2023-03-18T10:20:25.087

Your starting point should be to write an efficient prime number validator.

For example:

primeset = {2, 3}

def isprime(n):
    if n in primeset:
        return True
    if n < 2 or n % 2 == 0 or n % 3 == 0:
        return False
    f = 5
    while f * f < n:
        if n % f == 0 or n % (f + 2) == 0:
            return False
        f += 6
    primeset.add(n)
    return True

Then, to handle this particular case:

N = int(input('Enter number: '))

primes = []

for p in range(2, N+1):
    if isprime(p):
        primes.append(p)

print(len(primes))
print(primes)

Note: The sympy module has an isprime() function that will be much faster than this. This can be improved further with some more code. 2 is the only even prime number. Therefore you can check for that and subsequently (if necessary) start your range from 3 with a step of 2

How do you calculate the amount of prime numbers less than or equal to N?

3 Answers3