Codility - Lesson 10 Prime and composite numbers

Source Link:
https://codility.com/programmers/lessons/10-prime_and_composite_numbers/

Some Notes:
People have been analyzing prime numbers since time immemorial. A prime number is a natural number greater than 1 that has exactly two divisors (1 and itself).



In the above picture the primes are highlighted in white.


10.1. Counting divisors

Based on one divisor, we can find the symmetric divisor. One of these two divisors is less than or equal to sqr(n).Thus, iterating through all the numbers from 1 to sqr(n) allows us to find all the divisors.

10.1: Counting the number of divisors — O(sqr(n)).
1 def divisors(n):
2 i = 1
3 result = 0
4 while (i * i < n):
5 if (n % i == 0):
6 result += 2
7 i += 1
8 if (i * i == n):
9 result += 1
10 return result


10.2. Primality test

10.2: Primality test — O(sqr(n)).
1 def primality(n):
2 i = 2
3 while (i * i <= n):
4 if (n % i == 0):
5 return False
6 i += 1
7 return True

We assume that 1 is neither a prime nor a composite number, so the above algorithm works only for n ­ >= 2.