DEV Community

sridhar n
sridhar n

Posted on

Python Day 14 – Divisors, Prime Numbers and while...else

Day 14 was about divisors and prime numbers. Again, every problem came wrapped in a little story.

Divide the tiles equally

A teacher has 12 tiles and wants to split them into equal groups with nothing left over. 12 tiles can be made into:

  • 1 group of 12
  • 2 groups of 6
  • 3 groups of 4
  • 4 groups of 3
  • 6 groups of 2
  • 12 groups of 1

So the answer is just the divisors of 12: 1, 2, 3, 4, 6, 12.

Micro first

no = 12
divisor = 1
if no % divisor == 0:
    print(divisor)
divisor = divisor + 1

if no % divisor == 0:
    print(divisor)
divisor = divisor + 1
# ...same thing again and again
Enter fullscreen mode Exit fullscreen mode

The same two steps keep repeating: check, then add 1. That's our loop.

Macro

no = 12
divisor = 1
while divisor <= no:
    if no % divisor == 0:
        print(divisor)
    divisor = divisor + 1
Enter fullscreen mode Exit fullscreen mode

Output: 1 2 3 4 6 12

A small optimisation

Every number is divisible by 1 and by itself. So we can skip those and only check the middle part.

And here's something I hadn't thought about: apart from the number itself, no divisor can be bigger than half the number.

  • 1000 → biggest other divisor is 500
  • 10000 → 5000
  • 101 → nothing above 50 can divide it

So we only need to check up to no // 2:

no = 12
divisor = 2
while divisor <= no // 2:
    if no % divisor == 0:
        print(divisor)
    divisor = divisor + 1
Enter fullscreen mode Exit fullscreen mode

Output: 2 3 4 6

For a big number, that's half the work gone.

The special lock number (prime check)

A number is "special" if it can only be grouped as 1 group of N or N groups of 1. 7 is special. 8 is not, because 8 can be made into 2 groups of 4.

That's just the definition of a prime number.

Version 1: count the divisors

Using the same loop as before, count how many divisors we find between 2 and no // 2. If we find none, it's prime.

no = 13
divisor = 2
count = 0
while divisor <= no // 2:
    if no % divisor == 0:
        count = count + 1
    divisor = divisor + 1

if count == 0:
    print(no, 'is a prime number')
else:
    print(no, 'is not a prime number')
Enter fullscreen mode Exit fullscreen mode

Output: 13 is a prime number

It works, but it's wasteful. If the number is 1000, we already know it's not prime at divisor 2. There's no need to keep checking 3, 4, 5 ... 500.

Version 2: break + while...else

As soon as we find one divisor, we can stop. That's what break is for.

Then there's something I didn't know Python had: else on a while loop.

no = 13
divisor = 2
while divisor <= no // 2:
    if no % divisor == 0:
        print("Not a Prime Number")
        break
    divisor = divisor + 1
else:
    print("Prime Number")
Enter fullscreen mode Exit fullscreen mode

How it works:

  • If the loop hits break, the else part is skipped
  • If the loop finishes normally (the condition became false), the else part runs

So "the loop finished without finding any divisor" means prime. No count variable needed.

One case I checked: for no = 2, no // 2 is 1, so 2 <= 1 is false straight away. The loop never runs, the else runs, and 2 is correctly reported as prime.

Secret VIP numbers (first 5 primes)

A VIP number can only be divided by 1 and itself. Display the first 5 of them.

Expected: 2, 3, 5, 7, 11

In class we first wrote the prime check out again and again for no = 2, no = 3, no = 4, no = 5... and the repeating block was obvious. The whole prime check is the thing to loop.

So we put a loop inside a loop:

vip_count = 0
no = 2
while vip_count < 5:
    divisor = 2
    while divisor <= no // 2:
        if no % divisor == 0:
            break
        divisor = divisor + 1
    else:
        print(no, end=' ')
        vip_count = vip_count + 1
    no = no + 1
Enter fullscreen mode Exit fullscreen mode

Output: 2 3 5 7 11

Things to notice:

  • The outer loop moves through numbers 2, 3, 4, 5, ...
  • The inner loop checks whether the current number is prime
  • divisor = 2 has to be reset inside the outer loop. Otherwise the second number would start checking from wherever the first one stopped.
  • We stop when we have found 5 primes, not at a fixed number. We don't know ahead of time how far we'll have to go.

The "micro to macro" rule really earned its place today. Writing the repeated blocks by hand first made the nested loop feel obvious instead of scary.

Top comments (0)