CODEWITHSUNDEEP
pythonfor-loop
Deersfeet
Deersfeet

Reputation: 61

Prime number finder including 2 multiple times

This program makes a list of all prime numbers less than or equal to a given input.

Then it prints the list.

I can't understand why it includes the number 2. When I first designed the program, I initialized the list with primes = [2] because I thought, since 2 % 2 == 0, 

if n % x == 0:
    is_prime = False

will set is_prime to False. However, that doesn't seem to be the case.

I'm sure there is something going on with the logic of my range() in the for loops that I just don't understand.

I guess my question is: Why is 2 included in the list of primes every time?

import math


limit = int(input("Enter a positive integer greater than 1: "))

while limit < 2:
    limit = int(input("Error.  Please enter a positive integer greater than 1: "))

primes = []

#Check all numbers n <= limit for primeness
for n in range (2, limit + 1):
    square_root = int(math.sqrt(n))
    is_prime = True

    for x in range(2, (square_root + 1)):
        if n % x == 0:
            is_prime = False

    if is_prime:
        primes.append(n)

#print all the primes
print("The primes less than or equal to", limit, "are:")
for num in primes:
    print(num)

Upvotes: 1

Views: 359

Answers (1)

MSeifert
MSeifert

Reputation: 152695

Because you don't enter the second for-loop when you test for n=2 and therefore you don't set is_prime = False.

# Simplified test case:
x = 2
for idx in range(2, int(math.sqrt(x))+1): 
    print(idx)

This doesn't print anything because range is in this case: range(2, 2) and therefore has zero-length.

Note that your approach is not really efficient because:

  • you test each number by all possible divisors even if you already found out it's not a prime.
  • you don't exclude multiples of primes in your tests: if 2 is a prime, every multiple of 2 can't be prime, etc.

There are really great functions for finding prime numbers mentioned in Fastest way to list all primes below N - so I won't go into that. But if you're interested in improvements you might want to take a look.

Upvotes: 1

Related Questions