How to count the number of prime numbers?

Question

I am trying to store the output of the below code into a list

lower = int(input("Enter the begining of the range: "))
upper = int(input("Enter the end of the range: "))
print("Prime numbers between", lower, "and", upper, "are:")

for num in range(lower, upper + 1):
   if num > 1:
       for i in range(2, num):
           if (num % i) == 0:
               break
       else:
           numlist = []
           numlist.append(num)
           print(numlist)

I am expecting the output to be inside a list [p1, p2, p3,...pn]. However, I end up with the following:

Enter the begining of the range: 1
Enter the end of the range: 10
Prime numbers between 1 and 10 are:
[2]
[3]
[5]
[7]

Is this approach correct or are there better ways to meet the requirement? I am also trying to add a line of code that will let the user that there (4) numbers that are prime between 1 and 10.

You're creating a new `numlist` every time the inner loop breaks, replacing the previous one and you're printing it every time after you append a value. Create the list outside and before the outer loop and print it only once, outside and after the outer loop. This way, you'll have access to the list of results after the loop and printing its `len()` solves the second problem. — Grismar, Jan 05 '21 at 22:43
Be aware that there are much faster ways of creating a list of primes. Not clear if that's important to you or not. — Mark Ransom, Jan 05 '21 at 22:45
Adding to @MarkRansom, the typical (and most understandable) solution to for "all primes in a range" is a Sieve of Eratosthenes. It can be implemented in various ways (from "more efficient than trial division but maybe a bit memory hungry" to "*much* more efficient than trial division"). — ShadowRanger, Jan 05 '21 at 23:26
@ShadowRanger a naive sieve will be a memory hog but it needn't be. See https://stackoverflow.com/q/62899578/5987. — Mark Ransom, Jan 06 '21 at 00:26
@MarkRansom: Yar. I've implemented all of them, from the textbook original form to hyper-optimized segmented versions that further reduce memory usage by storing primality of blocks of 30 numbers in a single byte. The point is, iterative trial division (that doesn't store the result) need not have *any* memory storage beyond a trivial few individual values at any given time. Sieve of Eratosthenes must have a non-trivial amount of memory usage, which grows as you try to improve performance and test more numbers, but it's highly amenable to optimizations that keep the cost reasonable. — ShadowRanger, Jan 06 '21 at 00:36
Thank you, guys! Appreciate it the help. The code works just fine. — Mozart, Jan 06 '21 at 04:55

score 0 · Answer 1 · answered Jan 05 '21 at 23:16

just define array at the top and print at the bottom everything done.

lower = int(input("Enter the begining of the range: "))
upper = int(input("Enter the end of the range: "))

print("Prime numbers between", lower, "and", upper, "are:")
numlist = [] #this line
for num in range(lower, upper + 1):
   if num > 1:
       for i in range(2, num):
           if (num % i) == 0:
               break
       else:
           
           numlist.append(num)
          

print(numlist) # and this line

Alain T. · Answer 2 · 2021-01-07T17:39:16.563

To make this run fast, you should use the Sieve of Eratosthenes. It can be applied to a range of numbers using a partial sieve bitmap corresponding to the range of numbers:

def primesInRange(a,b):
    isPrime = [True]*(b-a+1)                  # partial sieve
    if a < 2: isPrime[:2-a] = [False]*(2-a)   # 0 and 1 are not primes
    for p in (2,*range(3,int(b**0.5)+2,2)):   # scan divisors up to √b
        base = (p - a%p)%p + p*(p>=a)         # first multiple in partial sieve
        isPrime[base::p] = [False]*len(isPrime[base::p])    # flag non-primes
    return [p for p,prime in enumerate(isPrime,a) if prime] # return primes

primes = primesInRange(150,200)

print(*primes)
# 151 157 163 167 173 179 181 191 193 197 199

print(len(primes))
# 11

print(len(primesInRange(100100000,100200000))) # speed challenge
# 5493

How to count the number of prime numbers?

2 Answers2