CODEWITHSUNDEEP
python
Fedo
Fedo

Reputation: 35

Python prime numbers for noobies

starting learning python and now encountered the prime number quiz. As I couldn't do it by my self, I looked up lots of answers and this was one of the easiest answers:

#Take the input from the user:   
lower = int(input("Enter lower range: "))  
upper = int(input("Enter upper range: "))  

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

Now my problem is I couldn't understand the statement of the second loop

for i in range(2,num):

I understand we need to do a second check for numbers that are not divided by 2 but are divided by 3,5,7 etc. (like 9, 15, etc.) But I cant seem to wrap my head around what that loop does. tried looking for more detailed explanation but it seemed my English isn't keeping up with the tutorials(my 3rd language)

So if anyone can take his/her time to explain to a low level English speaker as simply as possible ill be so grateful.

Upvotes: 1

Views: 1118

Answers (5)

oskros
oskros

Reputation: 3285

The second loop goes through all numbers between 2 and num-1, and check if num is dividable with each number (num%i==0) - if it is dividable, it cannot be a prime number and thus the loop breaks.

When you have an else statement after a for loop, that is only called in case the if statement inside the for loop was always false (i.e. num is a prime number)

It should be noted that the solution above is very unoptimized, and you can find primes much faster with something like the code below (and even faster than this if you want to use some very sophisticated code, but it is probably out of scope of this reply)

def is_prime(n):
    if (n % 2 == 0 and n > 2) or n < 2:
        return False
    return all(n % i for i in range(3, int(n**0.5) + 1, 2))

Explanation: If number is divisible by 2 and larger than 2 then it cannot be prime. It also cannot be prime if it is smaller than 2

Then for all other cases, we check whether our number is divisible by each odd number between 3 and the square root of the number, while skipping all even numbers (since primes cannot be even, and odd numbers cannot be divisible by even numbers). The reason we only have to check up until the square root of the number, is because if the number is a NOT a prime, it can be factored into two other numbers num = a * b. Now both a and b cannot be greater than the square root of num, since then the product a * b would be greater than sqrt(n) * sqrt(n) = n. So at least one of the factors must be smaller than the square root, and thus we only need to check until the square.

.
Finding all primes below a certain limit:
In case you wish to find all primes below a certain limit, you should check out an algorithm called Sieve of Erastothenes. Example of that is given below

def primes_sieve(limit):
    limit += 1
    not_prime = set()
    primes = []

    for i in range(2, limit):
        if i in not_prime:
            continue

        for f in range(i*i, limit, i):
            not_prime.add(f)

        primes.append(i)

    return primes

Upvotes: 1

mazore
mazore

Reputation: 1024

I put some helpful comments

#Take the input from the user:   
lower = int(input("Enter lower range: "))  
upper = int(input("Enter upper range: "))  

for num in range(lower,upper + 1):  # go through every number in the given range  
   if num > 1:  # discard 1, 0, and negative numbers
       for i in range(2,num):  # go through every number (i) between 2 and the number we are testing (exclude 1 because every number is divisible by 1)
           if (num % i) == 0:  # see if the number we are testing is divisible by i, for example 8 is not prime because it is divisible by 2, and 18 is not prime because it is divisible by 3
               break  # if it is, the number we are testing is not prime
       else:  
           print(num)  # if 'break' was not run, print out the number because it is prime

Upvotes: 1

DigiLeon
DigiLeon

Reputation: 148

We know a number will be a prime number if and only if it is divisible by 1 and the number itself. If it is divisible by any number within the range from 2 to (number - 1) then it will not be a prime number.

So in the second loop of the given code we are checking whether the number is divisible by any number within the range 2 to (number - 1) or not.

Example 1: number = 5 i values = 2, 3, 4 So here none of the i values divides 5. So, 5 is a prime number.

Example 2: number = 6 i values = 2, 3, 4, 5 here 2 divides 6 so 6 is not a prime number.

Thank you.

Upvotes: 1

user14520680
user14520680

Reputation:

A for loop will run for each item in an iterable or generator. Now, it's not entirely necessary to know what that means, but basically,

for i in range(2, num):

will run the contents for each element called i in range(2, num). The range returns a generator starting at the first argument and ending at the second argument minus 1. So if num is 10, range(2, num) returns [2, 3, 4, 5, 6, 7, 8, 9].

Upvotes: 1

wasif
wasif

Reputation: 15478

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The first few prime numbers are N={2, 3, 5, 7, 11, ….}

The idea to solve this problem is to iterate the num from start to end using a for loop and for every number, if it is greater than 1, check if it divides i. If we find any other number which divides, print that value. So the second nested loop is there.

Upvotes: 0

Related Questions