Prime and Composite Numbers for app.codility.com/programmers Explained in C++
By: Chrysanthus Date Published: 7 Aug 2025
Category of Article : Technology | Computers and Software | Algorithm
A prime number is a natural number (counting number) greater than 1, that has exactly two factors, which are 1 and itself. Examples of prime numbers are 2, 3, 5, 7, 11, 13.
A related set of numbers are called composite numbers. A composite number is a natural number that has the two factors which are 1 and itself, and at least one other factor. Examples of composite numbers are, 4, 6, 8, 9, 10, 12, 14.
Complete factors of 4 are: 1, 4, 2, 2. Complete factors of 6 are: 1, 6, 2, 3. Complete factors of 8 are: 1, 8, 2, 4. Complete factors of 9 are: 1, 9, 3, 3. Complete factors of 10 are: 1, 10, 2, 5. Complete factors of 12 are: 1, 12, 2, 3, 4, 6. Complete factors of 14 are: 1, 14, 2, 7. And so on!
Note: 2 x 2 = 22 = 4; 3 x 3 = 32 = 9; 4 x 4 = 42 = 16; 5 x 5 = 52 = 25; 6 x 6 = 62 = 36; and so on.
The following table lists prime and composite numbers from 2 to 14 (inclusive):
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
In the table, the primes are highlighted in white and the composite numbers are shown in gray. Note that the first two counting numbers, 0 and 1 are not in the list.
Counting Factors of n
To count the number of factors of n, the easiest approach is to iterate through all the numbers from 1 to n, and check whether or not each one is a factor of n. The time complexity for this solution is O(n), i.e. all the n numbers (maximum).
O(n) Time Solution
The following program has a O(n) solution for n = 14:
#include <iostream>
using namespace std;
int nSolution(int n) {
int noFactors = 0;
for (int i=1; i<=n; i++) {
if (n%i == 0)
noFactors += 1;
}
return noFactors;
}
int main(int argc, char **argv)
{
int N = 14;
int ret = nSolution(N);
cout << ret << endl;
return 0;
}
(n%i == 0) means that the remainder of n divided by i is equal to 0. The output is 4. It can be verified from the above table that the number of factors for 14 is 4, which are 1, 2, 7 and 14 itself.
Note: in the for-loop, i begins from 1, because division by zero is not allowed.
O(√n) Time Solution
The table for the prime numbers of n = 14 and n = 16 are given below:
|
n = 14 |
||||||||||||
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
n = 16 |
||||||||||||||
|
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
In this topic, O(n) time complexity is long, in order to determine the number of factors of a number (integer). It is possible to iterate up to, and including the square root or not including the square root, of the number (e.g. 14 or 16), depending on whether the number is a perfect square or not. 4, 9, 16, 25, 36, etc. are perfect squares, because their square roots do not have fractions. 14 is not a perfect square, because its square root, being equal to 3.74 (approximately) has a fraction. 0.74 is a fraction (proper fraction).
Note: factors of any number are always paired. The factors of 14 are: 1, 14, 2, 7. So, 1 and 14 are paired, because 1 x 14 = 14. Also, 2 and 7 are paired because 2 x 7 = 14.
The factors of 16 are: 1, 16, 2, 8, 4, 4. So, 1 and 16 are paired, because 1 x 16 = 16. 2 and 8 are paired because 2 x 8 = 16. 4 and 4 are paired because 4 x 4 = 16. Remember that 16 is a perfect square, whose square root is 4.
For each pair, one factor is below the square root of the number and the other factor is above the square root of the number. For a perfect square, the square root occurs two times (twice).
Consider 14 for example: The square root of 14 is about 3.74. So, 1 is below 3.74 and 14 is above 3.74, for a pair. Two is below 3.74 and 7 is above 3.74 for a pair. The square root, 3.74 itself, is not a factor of 14, because it has a fractional part.
Consider 16 as another example: The square root of 16 is 4. So, 1 is below 4 and 16 is above 4, for a pair. Two is below 4 and 8 is above 4 for a pair. 4 is at 4, the square root of 16 and the other 4 is till at 4, the square root of 16. The square root 4, is a factor of 16. The same value of 4 occurs twice.
Note: The square root of a number, n is not up to half of the number (½ x n). The square root of 14 is 3.74, which is not up to half of 14, which is 7. The square root of 16 is 4, which is not up to half of 16, which is 8. Exceptions to this are the square root of numbers from 4 downwards.
O(√n) Time Algorithm
Iterating from 1 to √n takes less time, than iterating from 1 to n. Since factors occur in pairs, in order to find the number of factors in n, just iterate from 1 to √n, and multiply the number of factors obtained by 2. This takes O(√n) time complexity, ignoring the constant time for multiplying by 2.
Code for Counting Number of Factors in √n Time
Well, in practice, while iterating from 1 towards √n, the count is just doubled (counting is done in 2’s instead of 1’s). A check is finally made if n is a perfect square. If it is a perfect square, then 1 and not 2 is added to the total count. This is because, for example, in the list of natural numbers from 1 to 16, 4 which is the square root of 16, should be counted once and not twice, because 4 x 4 is 16. The other pairs are of different integers. For example, 2 x 8 = 16 consists of 2 and 8 (one occurrence has to be multiplied by 2). The solution function is
#include <iostream>
using namespace std;
int sqrSolution(int n) {
int i = 1;
int noFactors = 0;
while (i * i < n) { //i is lower factor. Square root not included here
if (n % i == 0) {
noFactors = noFactors + 2; // counting in 2's
}
i = i + 1;
}
if (i * i == n)
noFactors += 1; //adds square root that counts once, if perfect square
return noFactors;
}
An input of 14 will give 4, and an input of 16 will give 5.
Primality Test
The primality test, tests whether or not a number is a prime number. A number (integer) is either a prime number or a composite number. 14 is a composite number because, between 2 and 13 (inclusive), there is at least one number that is a factor of 14. The factors of 14 are more than 2, which are 1, 14, 2, 7. Sixteen is a composite number, because between 2 and 15 (inclusive) there is at least one number that is a factor of 16. The factors of 16 are more than 2, which are 1, 16, 2, 8, 4. Note: 4 should be counted once, though it occurs twice (repeating).
Seventeen is a prime number because between 2 and 16 (inclusive), there is no factor for 17. The factors of 17 are only 1 and 17. Nineteen is a prime number because between 2 and 18 (inclusive), there is no factor of 19. The factors of 19 are only 1 and 19.
So, to know if a number, n is a prime number, scan from 2 to √n, to see if there is any factor of n in the range. If there is any factor in the range from 2 to √n (inclusive), then the number, n is a composite number and not a prime number; otherwise, n is a prime number. This scanning is done in O(√n) time complexity. Remember that factors occur in pairs, with one of the paired number below √n, and the other above √n. If n is a perfect square, then √n is a factor, counted once (not multiplied by 2) for primality test. There is no need to scan from 2 to n-1, since factors occur in pairs, with √n counted once, in the whole natural number range, if n is a perfect square.
O(√n) Time Code for Primality Test
The program code is:
#include <iostream>
using namespace std;
bool primality(int n) {
int i = 2;
int noFactors = 0;
while (i * i <= n) { //include test for √n because of =
if (n % i == 0) {
return false; // stop and return as soon as a factor is encountered (composite)
}
i = i + 1;
}
return true; //prime; else false had been returned if factor was encountered
}
int main(int argc, char **argv)
{
int ret1 = primality(14);
int ret2 = primality(16);
int ret3 = primality(17);
int ret4 = primality(19);
cout << ret1 << ", " << ret2 << ", "<< ret3 << ", "<< ret4 << endl;
return 0;
}
The function returns false for non-prime number (composite number) and true for prime number. The output is:
0, 0, 1, 1
where 0 means false and 1 means true.
Exercise
Problem: Consider n coins aligned in a straight row, spread out, such that one person can stand behind one coin. The values of the coins are 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Each coin is showing head, at the beginning. The initial states of the coins are shown in the following table:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
The gray background color of each cell, indicates the head-up of each coin. Then, n people turn over corresponding coins as follows. Person i reverses coins with numbers that are multiples of i. That is, person i flips coin i, flips coin 2 x i, flips coin 3 x i, . . . until no more appropriate coin remains (at the right end), for that person to flip. After that, person 2 does a similar thing, to the right end of the list; and so on. The goal is to count the number of coins showing tails, when all flippings are over. In this problem, the final configuration is:
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Among the 10 people, each person does coin flipping. The cells with the background color of white, are the coins with tails up, at the end of the exercise. The number of tails is 3. Your code should return 3. Use the fastest algorithm you can determine, for the solution.
Notes:
Person 1 flips his coin and all its multiples. Then person 2 flips his coin and all its multiples. Then person 3 flips his coin and all its multiples. This continues until person 10.
- Person one flips coin 1, flips coin 2, flips coin 3, flips coin 4, flips coin 5, flips coin 6, flips coin 7, flips coin 8, flips coin 9, flips coin 10, to show all tails. All these numbers are multiples of 1.
- Person two flips coin 2, flips coin 4, flips coin 6, flips coin 8, flips coin 10. These are multiples of 2. These particular coins are now showing heads again.
- Person three flips coin 3, flips coin 6, flips coin 9.
- Person four flips coin 4, flips coin 8.
- Person five flips coin 5, flips coin 10.
- Person six flips coin 6. He cannot flip coin 12, because there is no coin 12.
- Person seven flips coin 7.
- Person eight flips coin 8.
- Person nine flips coin 9.
- Person ten flips coin 10.
The following table shows the heads and tails of the flips, beginning from person 1, going downwards:
|
person |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
2 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
3 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
4 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
5 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
6 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
7 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
8 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
9 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
10 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
The last table row shows the final states of the heads and tails of the coins.
Brute Force Approach
The brute force (direct) approach has O(n.log2(n)) time complexity. This consists of the counting (summing) of the number of times, each coin was changed. From the above table, this is 27 times. When n = 10, O(n.log2(n)) = O(10.log2(10)) = 33 approximately. As 27 is slightly less than 33, we say the brute force approach, has O(n.log2(n)) time complexity, by just coding the number of changes above.
Algorithm for Brute Force Approach
An array (vector) of n+1 cells, with all cells initialized to zero, is created. The values on the coins are from 1 to 10, and not 0 to 10. The indexes for the array represents the values of the coins. There is no coin with 0 value. So, the 0 index of the array is there for convenience, since zero based indexed array cell counting, begins from 0. With the exception of cell 0, the value of each cell of the array is a counter, that counts the number of times its coin has been flipped.
If the number of flips for a coin is even, then the coin will end up, head up. If the number is odd, then the coin will end up, tail up.
The goal is to count the number of coins showing tails up at the end (last row above). So, while the list is scanned from 1 to 10 (inclusive), corresponding counters of the array are incremented. Before going to the next iteration set, it is determined if the current cell counter value is odd or even. If it is odd, the number for the number of tails, is incremented. This tail counter (different from the indexes) is the number of tails at end of exercise (last row of table above). The brute force program, which also counts the number of operations (flips), is
#include <iostream>
#include <vector>
using namespace std;
int bruteCoins(int n) {
int noTails = 0; //no. of tails counter; refers to last row in table
vector<int> counters(n+1, 0);
int noOperations = 0;
for (int i=1; i<=n; i++) {
for (int j=i; j<=n; j = j + i) { //flip the multiples
counters[j] = counters[j] + 1; //increment the different counters
noOperations++;
}
if (counters[i] % 2 == 1) {
noTails++; //refers to last row in table
}
}
cout << "No. of operations: "<< noOperations << endl;
return noTails;
}
int main(int argc, char **argv)
{
int N = 10;
int ret = bruteCoins(N);
cout << "No. of tails: "<< ret << endl;
return 0;
}
The output is:
No. of operations: 27
No. of tails: 3
The reader should read through the code and comments, if that is not already done. The n number of operations to initialize each cell of the vector, counters, is not included in the time complexity of O(n log n). These initialization to 0 is done internally by C++.
It must interests the reader that for this problem, the brute force solution gives O(n.long2n) number of operations (27 compared to 33), which is considered as high; while in other problems such as sorting, O(n.long2n) is a good time complexity.
O(√n) Solution
The square-root of 10 is 3.2 approximately, while log2(10) is approximately 3.3. The numbers are close in this case.
Observe that each coin will be turned over exactly as many times as the number of its factors (by different "preceding" persons). That is, from the last table above (going downwards):
- Coin one is flipped once, with number of factors, 1: factors are 1 and 1 (1 occurring twice but counted once).
- Coin two is flipped twice, with number of factors, 2: factors are 1 and 2.
- Coin three is flipped twice, with number of factors, 2: factors are 1 and 3 (person 2 skipped coin 3).
- Coin four is flipped three times, with number of factors, 3: factors are 1, 4, 2, 2 (2 occurring twice but counted once - person 3 skipped coin 4).
- Coin five is flipped two times, with number of factors, 2: factors are 1, 5 (person 2, person 3 and person 4 skipped coin 5).
- Coin six is flipped four times, with number of factors, 4: factors are 1, 6, 2, 3. (person 1, person 2, person 3, and person 6 flipped coin 6)
- Coin seven is flipped two times, with number of factors, 2: factors are 1, 7. (person 1 and person 7 flipped coin 7)
- Coin eight is flipped four times, with number of factors, 4: factors are 1, 8, 2, 4. (person 1, person 2, person 4, and person 8 flipped coin 9)
- Coin nine is flipped three times, with number of factors, 3: factors are 1, 9, 3, 3 (3 occurring twice but counted once). (person 1, 3, and 9)
- Coin ten is flipped four times, with number of factors, 4: factors are 1, 10, 2, 5. (person 1, person 2, person 5, and person 10 flipped coin 10)
As can be seen from this listing, each coin is flipped, as many times as its number of factors. The coins that are flipped an odd number of times show tail, meaning that it is sufficient to find the coins with an odd number of factors. The coins with odd number of factors from this listing are: 1, 4, and 9, agreeing with the last table above. These are perfect squares. Do not forget that 1 is a perfect square (1 x 1 = 1). The coins that are flipped an even number of times show head.
A number, i, e.g. 16 with odd number of factors, has to be a perfect square, having its highest factor, k2 = i => k = √i . A number, i, e.g. 8 with even number of factors, is not a perfect square. 16 is not in the list; it has been used here just for illustration.
Now, factors of integers occur in pairs of small and big, on opposite sides of √n, except for perfect square numbers, where the highest factor less than n, occurs twice and is counted once. n is 10 for the above problem. √10 = 3.2 approximately.
Now,
12 = 1
22 = 4
33 = 9
42 = 16, and above 10
We know in advance that the result (values for number of tails) are 1, 4 and 9, which are squares for 1, 2, and 3, all of which are numbers less than or equal to √10. We know in advance because their squares are less than 10.
So if the list is scanned from 1 to √n, while squaring to see if the square is not above 10, then the number of tails up, at the end of the exercise, are obtained. This number is the integer counting from 1 to less than or equal √n, where n is 10 in this exercise. With all that, O(√n) time complexity is used to find the number of tails up, at the end of the exercise.
So, number of integers from 1 to less than or equal √n, whose squares are less than or equal to n, is the number of integers (perfect squares) in the range 1 to n (inclusive), with odd number of factors. Above, these perfect squares are 1, 4 and 9; three numbers altogether. The corresponding roots are 1, 2 and 3. So, the numbers 1, 2 and 3 should be counted. The smart program, which also counts the number of operations (flips), is:
#include <iostream>
#include <vector>
using namespace std;
int bruteCoins(int n) {
int noTails = 0;
int noOperations = 0;
for (int i=1; (i*i <= n); i++) { //number of operations will never go above square root of n
noTails++;
noOperations++;
}
cout << "No. of operations: "<< noOperations << endl;
return noTails;
}
int main(int argc, char **argv)
{
int N = 10;
int ret = bruteCoins(N);
cout << "No. of tails: "<< ret << endl;
return 0;
}
The output is:
No. of operations: 3
No. of tails: 3
Note: i*i in the while condition, means i x i = i2 . The limit for iterating is decided by the while-condition. The reader should read through the code, if he/she has not already done so.
Conclusion
A prime number is a natural number (counting number) greater than 1, that has exactly two factors, which are 1 and itself. A composite number is a natural number that has the two factors which are 1 and itself, and at least one other factor. Factors of any number occur in pairs, a small one and a big one, on both sides of √n. For perfect square numbers, though the square root is a pair of the same number, the square root is counted once. And so perfect square numbers are said to have an odd number of factors, while non-perfect square numbers are said to have an even number of factors.
The following should interest the reader: log21 = 0, √1 = 1; log24 = 2, √4 = 2; log28 = 3, √8 = 2.83 approximately; log29 = 3.17 approximately, √9 = 3; log216 = 4, √16 = 4; log264 = 6, √64 = 8; log2144 = 7.17 approximately, √144 = 12; log2256 = 8, √256 = 16. That is, log2n is about equal to √n for small integers; but for big integers, log2n is less than √n.