Python 4.3.1.9 LAB: Prime numbers - how to find them

 

Objectives

• familiarizing the student with classic notions and algorithms;
• improving the student's skills in defining and using functions.

Scenario

A natural number is prime if it is greater than 1 and has no divisors other than 1 and itself.

Complicated? Not at all. For example, 8 isn't a prime number, as you can divide it by 2 and 4 (we can't use divisors equal to 1 and 8, as the definition prohibits this).

On the other hand, 7 is a prime number, as we can't find any legal divisors for it.

Your task is to write a function checking whether a number is prime or not.

The function:

is called is_prime;

takes one argument (the value to check)

returns True if the argument is a prime number, and False otherwise.

Hint: try to divide the argument by all subsequent values (starting from 2) and check the remainder - if it's zero, your number cannot be a prime; think carefully about when you should stop the process.

If you need to know the square root of any value, you can utilize the ** operator. Remember: the square root of x is the same as x0.5

Complete the code in the editor.

Run your code and check whether your output is the same as ours.

Expected output

2 3 5 7 11 13 17 19

Before we create our function, let's know what is a prime number first.

Prime Number 

• It's a whole number/integer that is greater than 1.
• It's factors (multiplication factors) are 1 and itself ONLY. Different than this, then it's not a prime.
• If squared (3 ** 0.5) doesn't equal a whole number. 
• Prime % 2 = 1
• Except 2, prime numbers are odd numbers (prime % 2 = 1)

2 has only two factors (1 x 2)

3 has only two factors (1 x 3)

5 has only two factors (1 x 5)

4? (1 x 4, 2 x 2) .. 4 % 2 = 0 .. 4 ** 0.5 = 2   4 is NOT prime

Solution with Code

def is_prime(num):

    if num <= 1: # Prime number is a whole number greater than 1

        return False #If 1 or less, means it's NOT a prime number

    """ We start by 2 because every number is divisible by 1 and itself. We end the

    range by num which means the last number we divide by is

    the number before our number in hand (as indexing, num wont be included)"""

    for i in range(2, num): # We start dividing by 2 until num-1

        if num % i == 0: # If divisible with no remainders, then num has a divisor

                            other then 1 and itself, hen it's NOT prime.

            return False

            break # to avoid getting all the results of all i divisions in the loop

    else:

        return True

for i in range(1, 20):

        if is_prime(i + 1):

            print(i + 1, end=" ")

print()

Is there other sophisticated solutions? When you go up and read again the definition and rules for prime numbers, we can come up with a better faster solution

def is_prime(num):

    if num <= 1:

        return False

    elif num == 2: # 2 is always prime

        return True

    elif num > 2 and num % 2 ==0: # if the number is > 2 (since 2 is Prime)

                                    and number is even (num % 2 == 0),

        return False # It cannot be prime

    for d in range(2, round(num ** 0.5)): # d is the divisor factor

        if num % d == 0: # If the number is even, we will

                            find the divisor in the first step

            return False

    return True

for i in range(1, 20):

        if is_prime(i + 1):

            print(i + 1, end=" ")

print()

=================================================================================

Follow the Python page on the Blog to be the first to know ❤