Calculate the number of primes in a range

Question

I wrote some code to return how many prime numbers are in a specific range and what they are. It also tells you whether the number of primes is also a prime!

I feel like this seems like a fairly long winded approach for something that's probably very simple, can someone please tell me how I can improve this?

def prime_number():
    primes = []
    primes_2 = []
    low = int(input("What number would you like to start at? "))
    high = int(input("What number would you like to go up to? "))
    if int(low) == 1 and int(high) == 1:
        print("1 isn't a prime number dumb dumb")
    elif high < 2:
        print("Don't be annoying")
    else:
        for x in range(int(low), int(high)):
            for i in range(2, x):
                if (x % i) == 0 and x != i:
                    break
                elif (x % i) == 1 and i <= (x - 2):
                    continue
                elif (x % i) == 1 and i == (x - 1):
                primes.append(x)
            x = x + 1
        print("The number of prime numbers is: ", len(primes))
        for y in range(2, int(low)):
            for z in range(2, y):
                if (y % z) == 0 and y != z:
                    break
                elif (y % z) == 1 and z <= (y - 2):
                    continue
                elif (y % z) == 1 and z == (y - 1):
                    primes_2.append(y)
            y = y + 1
        if int(len(primes)) in primes or int(len(primes)) in primes_2:
            print("Huh, fancy that!", len(primes), "is also also a prime number!")
        print("The prime numbers are: ",primes)

Answer 1

Welcome to Code Review! Here are some suggestions.

Naming

Choose a better name than primes_2. I'm not clear on what this variable does.

Write some documentation

...in triple quotes at the top of your function. Describe its inputs and outputs.

Separate user input from processing

Put your calculation code in a separate function from your user input and output code.

Validation

If the user enters invalid input, consider looping until the input they provide is valid. Or, at least - return out of the function if it's invalid, instead of having a large else covering the rest of your code.

Increment-and-assign

Use x += 1 instead of x = x + 1.

Formatted output

Consider using this form instead:

print(f'Huh, fancy that! {len(primes)} is also a prime number!')

Answer 2

You have a problem with indentation in this line:

elif (x % i) == 1 and i == (x - 1):
primes.append(x)

f-strings:

if int(len(primes)) in primes or int(len(primes)) in primes_2:
    print("Huh, fancy that!", len(primes), "is also also a prime number!")
    print("The prime numbers are: ",primes)

you might want to replace this with f'strings that looks like this:

if int(len(primes)) in primes or int(len(primes)) in primes_2:
    print(f'Huh, fancy that! {len(primes)} is also a prime number!')
    print(f'The prime numbers are:\n{primes}')

Prime sieve

A much more efficient way of calculating prime numbers within a given range is using the sieve of Eratosthenes: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Bug:

your code does not include 2 as a prime number, it returns the following for range(0, 100): [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

For comparison purposes: (I included a part of your prime implementation in a new function)

def prime_slow(low, high):
    """Return a list of primes."""
    primes = []
    for x in range(int(low), int(high)):
        for i in range(2, x):
            if (x % i) == 0 and x != i:
                break
            elif (x % i) == 1 and i <= (x - 2):
                continue
            elif (x % i) == 1 and i == (x - 1):
                primes.append(x)
        x = x + 1
    return primes


if __name__ == '__main__':
    test_number = 10 ** 4
    start_time1 = perf_counter()
    prime_slow(0, test_number)
    end_time1 = perf_counter()
    print(f'Time to calculate primes (slow method): {end_time1 - start_time1} seconds.')
    start_time2 = perf_counter()
    list(prime_sieve(test_number))
    end_time2 = perf_counter()
    print(f'Time to calculate primes (using a sieve): {end_time2 - start_time2} seconds.')

• Time to calculate primes (slow method): 3.067288957 seconds.
• Time to calculate primes (using a sieve): 0.0016803199999997354 seconds.

The whole code might look like:

def prime_sieve(upper_bound):
    """Generate primes up to upper_bound."""
    primes = [True] * upper_bound
    primes[0] = primes[1] = False

    for index, prime in enumerate(primes):
        if prime:
            yield index
            for number in range(index * index, upper_bound, index):
                primes[number] = False


def prime_number():
    """Display number of primes within user specified range."""
    try:
        lower_bound = int(input('Enter starting number: '))
        upper_bound = int(input('Enter ending number: '))
        primes = prime_sieve(upper_bound)
        valid_primes = [prime for prime in primes if prime >= lower_bound]
        print(f'The number of prime numbers is: {len(valid_primes)}'
              f' prime numbers in range {lower_bound} to {upper_bound}')
    except ValueError:
        print(f'Invalid number!')
        print('Failed to calculate primes.')


if __name__ == '__main__':
    prime_number()

Answer 3

Since you compute the primes between low and high to get the number of primes

and

you compute the primes between zero and low to check if your len(primes) is prime, why not compute primes from zero to high in one shot? This also has the big advantage of increasing the speed of your computing speed (yes, you read that right).

Right now, to see if a number n is prime, you check if you can divide n by all the numbers "behind" it. So, for example :

Is 5 a prime?

Let's try to divide by 4,3,2,1

We can't, so 5 is prime.

It's alright when you check for 5, it's a very small number. How about 103? It's still pretty fast, how about 23321? It gets slower.

Is there a faster way we could check if a number is prime? If, for n, I already have all primes p smaller than n, we can verify primness using Prime Factorization an Dynamic Programming.

Here are non-formal definition of the two concepts above, if you don't want to click the links

Prime factorization : Any integer can be rewritten as a multiplication of prime numbers to a power p.

Examples :

$$4 = 2^2$$ $$288 = 2^5 * 3^2$$ $$45 = 3^2 * 5$$

I hope you get it.

Dynamic Programming : To fix a big problem, use a composition of smaller problem you already solved.

Want to see if 15 is prime (we know it's not)? But you already know all the prime numbers below, let's use that!

Primes under 15 : 2, 3, 5, 7, 11, 13

Using the definition of prime factorization, I can check if 15 is prime by dividing it only by the numbers above. This means instead of trying 14 divisions, we can do 6! Now, that ain't a big win, but is 23321 a prime? Instead of doing 23320 divisions, we can do only 2599 (because 23321 is the 2600th prime number). Now that's faster!

---

Doing this x = x + 1 in your loop is useless.

for x in range(int(low), int(high)):

# The rest of the code

x = x + 1

You add 1 to x, but it's overwritten straight after because of the for loop.

---

When you check for len(primes) is prime, you should realize that your code is fully duplicated from the code above. In such cases, you probably want to extract a function from your code like, is_prime to reduce the duplication. But, moreover, you don't want to find all when checking if a number is prime. What I mean is that you can stop your search once your number can be divided by any number below it.

---

Now for good practices, your method prime_numbers should take arguments named low and high, and do the input asking outside the function. What I mean is that using print in a method that doesn't have the responsibility to print stuff (See Single Responsibility Principle). Now, disclaimer, SRP catches lot of heat from some developers because it is easy to get over zealous with it. You need to be cautious not to separate everything in different functions/classes/etc. The idea is that you want your method to do what they're supposed to do ( = what their name is) and nothing else, because it's confusing for developers reading your code.

Answer 4

I won't repeat the excellent comments made by the other answers on Prime Factorization, Dynamic Programming, Single Responsibility Principle, Indentation, f-Strings, Bugs, Naming, Documentation, and Separation of Input from Processing.

Integer conversion

After all those comments have been filtered out, the following programming style still jumps out and needs to be addressed:

low = int(input("What number would you like to start at? "))
high = int(input("What number would you like to go up to? "))
if int(low) == 1 and int(high) == 1:
#...
    for x in range(int(low), int(high)):
    # ...
    for y in range(2, int(low)):
    # ...

What is up with all the calls to int(...)?

Both low and high have been converted to integers in the first two statements (or an exception has been raised if they can't be). You don't need int(low) and int(high); that is just being redundant and obfuscating.

Similarly:

    if int(len(primes)) in primes or int(len(primes)) in primes_2:

The length of a list is always an integer, so again the wrapping len(...) in int(...) calls does not add anything but clutter to the program.

Precedence

You've got more parenthesis than you need:

        elif (x % i) == 1 and i <= (x - 2):

Both the modulo-operation (%) and the subtraction-operation (-) are higher precedence than the comparison operators (== and <=), so the parenthesis may be safely omitted:

        elif x % i == 1 and i <= x - 2:

Limits & Looping

    for i in range(2, x):
        if (x % i) == 0 and x != i:

The range(2, x) object includes the starting point (2), but excludes the ending point (x). As such, i will never reach x, so the expression x != i will always be true, and may be omitted from the first if statement.

When i == x - 1, then x % i == 1 will always be true, so

elif (x % i) == 1 and i == (x - 1):

could simply be written as:

elif i == x - 1:

Except, what this really means is that the for i in range(2, x) has reached the end of the range without ever executing the break statement. For this you could use a for ... else loop.

        for i in range(2, x):
            if x % i == 0:
                break
        else:
            primes.append(x)

Finally, we can further simply this by realizing we are asking if any value in the range from 2 (inclusive) to x (exclusive) divides evenly into x ... and Python has an any() function. If any value in that range does, then x is not prime:

if not any(x % i == 0 for i in range(2, x)):
    primes.append(x)

If you were generating all of the primes, starting from 2 instead of starting from low, you could optimize this search by just testing for prime divisors:

if not any(x % i == 0 for i in primes):
    primes.append(x)