Chapter 13 Using ‘while’ Loop

Question Check whether a given number is prime.

We will first solve the problem using for loop and then improve it using while and other options.

13.1 STEP 1 - Go Small

Instead of trying big numbers, bring it down to something small and manageable (like “is 7 a prime number?”). What will you do to check whether 7 is a prime number? You divide by all integers from 2 to 6 and find whether any remainder is 0. If not, 7 is a prime.

You start with a variable answer and assign it to “prime.” As you go over the divisions, continually update answer.

# Is 7 a prime number?

answer="prime"

if((7%2)==0):
   answer="not prime"
if((7%3)==0):
   answer="not prime"
if((7%4)==0):
   answer="not prime"
if((7%5)==0):
   answer="not prime"
if((7%6)==0):
   answer="not prime"

print(answer)

This is exactly how you will teach a small kid to find prime numbers, right? Your first code should be similar to the simplest algorithm that you will teach to a small kid.

13.2 STEP 2 - Use Loop

Next we replace the repetitive code with a loop.

# Is 7 a prime number?

answer="prime"

for i in [2,3,4,5,6]:
   if((7%i)==0):
     answer="not prime"

print(answer)

13.3 STEP 3 - Use Range

Now that you have the simplified code, see whether you can replace the list range.

# Is 7 a prime number?

answer="prime"

for i in range(2,7):
   if((7%i)==0):
     answer="not prime"

print(answer)

Once you do that, you can easily change the code to check whether 97 or 972239 are primes.

# Is 97 a prime number?

answer="prime"

for i in range(2,97):
   if((97%i)==0):
     answer="not prime"

print(answer)

After you do that a few times, you will find replacing the number in multiple places a bit tiring. Why not turn it into a variable?

# Is 97 a prime number?

N=97
answer="prime"

for i in range(2,N):
   if((N%i)==0):
     answer="not prime"

print(answer)

13.4 Using “break” to Leave Loop Early

You can make many different adjustments once the code is working. For example, you know from math that there is no need to check all the way to 96 to find whether 97 is prime. You can stop at 97/2 or more correctly at the square root of 97.

However, the biggest improvment in a program to check for prime numbers come, if you stop right after the first remainder becomes 0.

All those changes can be made in steps, but first make sure your inefficient code is working. Do not introduce efficiency until you have working inefficient code.

Here is a slightly modified version of the previous code.

N=775

is_prime=True

for i in range(2,N):
        if(N%i==0):
                is_prime=False

print(is_prime)

We improve it by considering remainders for numbers from 2 to square-root of N. Moreover, we jump out of the loop as soon as the first remainder of 0 appears using “break.”

N=775

is_prime=True

for i in range(2,int(N**0.5)):
        if(N%i==0):
                is_prime=False
        break

print(is_prime)

13.5 Using “while” Loop

Another way to leave the loop early is to use “while” instead of “for.”

13.6 Example 2. Check whether a number can be expressed as sum of squares

Here you use “break” if you want only one example of sum of squares. If you want every possible sum of squares, do not use “break.”

num=29

answer=False

limit=int(num**0.5)

for i in range(limit):

        diff=num-i*i
        sq=int(diff**0.5)

        if(sq*sq + i*i ==num):
                print(sq, i)
                answer=True

print(answer)