Problem Solving: Composites, Primes and Prime Factorization
Learn to write a program that finds whether a number is prime or composite.
We'll cover the following
 Prime numbers and composite numbers
Prime numbers and composite numbers
Prime number: Any positive integer (other than 1 and 0) that is divisible by 1 and itself is called a prime number. For example, 2, 3, 5, 7, 11, 13,… are prime number sequences.
Composite numbers: All the other positive numbers (4, 6, 8, 9, 10, 12, 14, 15,… ) other than 0 and 1 are called composite numbers.
1 and 0 are neither prime nor composite.
Computing compositeness of a number
Let’s write a function isComposite
fucntion of bool
return type, which should take a number n
as a parameter, and it should return true
if n
is composite; otherwise, false
.
The function must handle the following:

It should return
false
in case the number is 1. 
A composite number must at least be divisible by itself and a number other than 1. In other words, if we exclude 1 and the number
n
itself,n
must be divisible by at least one number.
Implementation
To determine whether a number n
is composite or not, we can take its mod, (%
), with all the numbers, starting from 2
till ‘1 less than the number n' to see whether
n` is completely divisible by any other number.
We can create a count
variable initialized to 0
, which is incremented whenever 0
is completely divisible by some number.
We can write a for
loop with an if
condition, which checks the divisibility of a number n
by taking its mod with number 2
to number n1
(not checking with the number itself and 1).
If the number n
is divisible by at least one number from 2
to number n1
, with the remainder equal to 0
, count
will be incremented.
We can write an if
statement that checks if count > 0
, Next, we, return true
if the number qualifies to be a composite number, and we have found it’s at least one divisor.
Otherwise, we return false
. This means the number n
is not composite (but is prime).
Exercise: Try it yourself
Now that we know what to do, try and write the code for isComposite()
below.
bool isComposite(int n){int count = 0;// Add code here}
Computing primality of a number
We’ll write several implementations of primality testing.
Implementation 1: Improvising composite function
Now, what if we want the function to tell whether a number is a prime number or not? Can we change the above function of bool isComposite(int n)
a little bit to get the desired function?
The difference between prime and composite is just one for prime, the count
of the divisors other than 1 and itself (n
), is zero. So what changes should we make in the above function which you wrote?
You guessed it! We’ll simply return false
if count > 0
and true
if n
isn’t divisible by any number other than 1
and n
itself.
Our isPrime()
function would then be as follows:
bool isPrime(int n){if(n <= 1)return false;int count = 0;for (int d = 2; d < n; d++){if (n % d == 0){count++;}}if(count > 0)return false;elsereturn true;}
Consider the following lines of code:
if(count > 0)
return false;
else
return true;
We can rewrite the code above as follows
return count == 0;
It’s not only concise but also more efficient! count == 0
is just one expression that either evaluates to true
or false
depending on the value of the count
.
Implementation 2: Immediately return the verifier when found
Notice that we don’t necessarily need the counting of divisors? The divisor acts as/a verifier that we have found a divisor. Hence, the given number is not a prime number, so why should we keep iterating the loop? We can immediately return the verifier if the given number n
is divisible by any number within the checking range.
Using the above idea, we have our second implementation as follows.
bool isPrime(int n){if (n < 2)return false;for (int d = 2; d < n; d++){if (n % d == 0){return false;}}return true;}
Let’s add this function and run our complete program:
#include <iostream> using namespace std; int isPrime(int n) { if(n <= 1) return false; for (int d = 2; d < n; d++) { if (n % d == 0) { return false; } } return true; } int main() { int num; cout << "The number: "; cin >> num; cout << num << " is "; if(isPrime(num)) cout << "prime number."<< endl; else cout << "not a prime number."<< endl; return 0; }
There is a logical error in the code below that is common among beginner programmers. Let’s see if you can figure that out in the following code:
Quiz: Identify the logical error
Can we rewrite the above isPrime()
code as below?
In case you don’t find the error, copy this code in the code editor below and execute it step by step to spot the logical error.
bool isPrime(int n)
{
if (n <= 1)
return false;
for (int d = 2; d < n; d++)
{
if (n % d == 0)
return false;
else
return true;
}
}
Instruction: Add the above isPrime()
code snippet (of the quiz) in the code editor below and execute it step by step, in case you want to confirm the error.
#include <iostream> using namespace std; int count = 0; bool isPrime(int n) { // Add code here } int main() { int num; cout << "The number: "; cin >> num; if(isPrime(num)) cout << "prime number."<< endl; else cout << "not a prime number."<< endl; return 0; }
Implementation 3: Shrinking ranges
Let’s now discuss several versions in which we’ll gradually reduce the search space of finding the verifier if the number is not a prime number.
1. Reducing search space to half
Instead of checking for all the numbers from d = 2
to d < n
, we could check from d = 2
to d < n/2
which means the number of comparisons is reduced by half.
If a positive odd integer $n$ is given, any integer greater than $1$ multiplied by a number $t$, where $t \gt \lceil\frac{n}{2}\rceil$, will yield a value greater than $n$. For example, if $n$ is $12$, then $7\times 2 = 14$, $8 \times 2 = 16$, and so on.
If n
was 9
, the condition would become d < 4
.
bool isPrimeV1(int n){if(n <= 1)return false;if(n!=2 && n%2==0)return false;// because for n = 4 the loop won't execute and checking from 2 will be missed.for(int d=2; d < n/2; d++){if(n % d == 0)return false;}return true;}
The code above would still get the job done and is more efficient than the previous implementation (at least we have reduced half of the divisions).
However, interestingly enough, we can still make it more efficient!
2. Reducing search space by only divisions by odd numbers and 2
We can deal with the even numbers separately; if the number n
is an even number and not 2
, then we can return false
.
If a positive integer
n
is not divisible by2
, then it will never be divisible by any other even number, such as 4, 6, 8, 10, and so on. This would help reduce the number of iterations further, making it more efficient.
bool isPrimeV2(int n){if(n <= 1)return false;if(n != 2 && n % 2 == 0)return false;for(int d = 3; d < n/2; d+=2){if(n % d == 0)return false;}return true;}
As we reduced the space to half, we can ask ourselves ‘is there a way we can shrink the space further?" Think about it.
3. Shrinking the search space within one third
The idea is inspired by a simple mathematical fact:
If
n
is an odd number and its not divisible by 3, then any number bigger than $\frac{n}{3}$ cannot dividen
. You can test this on odd numbers which are not divisible by 2 and 3.
This brings us to our new implementation. So, our condition in the for
loop can then be d < n/3;
along with our incremental step of d += 2
.
bool isPrimeV3(int n){if(n <= 1)return false;if(n!=2 && n%2==0)return false;if(n!=3 && n%3==0)return false;for(int d=3; d<n/3; d+=2){if(n%d==0)return false;}return true;}
Before we move to the next best improvement, look at the following scenario. Let’s say we would like to test primality for 101. How do we test it? We do the following division testing:
2 x 50 = 1003 x 33 = 994 x 25 = 1005 x 20 = 1006 x 16 = 967 x 14 = 988 x 12 = 969 x 11 = 9910 x 10 = 10011 x 9 = 9912 x 8 = 98...
For a complete divisor $d$, we look for the largest integer quotient $q$, which, if we increase any further, the multiple of $d \times q$ will exceed $n$. If you look at $d$ and $q$ closely, $d$ is increasing, and $q$ is decreasing until $d$ and $q$ are almost together. What is the exact number where both $d$ and $q$ will reach?
4. Reducing search space to $\sqrt{n}$
We know that $\sqrt{n} \times \sqrt{n} = n.$
Theorem: For any composite number $n$, the first divisor $d$ cannot be greater than $\sqrt{n}$.
Proof: Let’s prove by contradiction that the first factor is greater than $\sqrt{n}$. By definition, $n$ is not a prime number, then, $n = d \times q$ where both $d$ and $q$ are greater than $\sqrt{n}$. Then $d>\sqrt{n}$ and $q > \sqrt{n}$ which makes $d \times q > n$. This is a contradiction.
So we see that the divisor of n
cannot be greater than $\sqrt{n}$.
That brings us to our even better implementation.
bool isPrimeV4(int n){if(n <= 1)return false;for(int d=2; d<=sqrt(n); d++) // sqrt(n) times sqrt(n) will be called{if(n%d==0)return false;}return true;}
Here sqrt(n)
is the function that we created in the previous lesson to find the square root of the number n
.
There’s a little issue with the code given above in terms of efficiency. Observe the code above and find out what it is.
We hope you figured out the issue. The condition, d <= sqrt(n)
in our for
statement calls the sqrt(n)
function in each iteration. This means sqrt(n)
is computed each time, and then the result is assigned to the e d
variable, which makes our code inefficient.
5. Limitation in $\sqrt{n}$ with odd numbers divisibility and 2
So instead of calling the sqrt(n)
function in the condition, we could make a new variable called limit
and simply assign it the result of sqrt(n)
. We’ll also add conditions of evenness before the main loop and check only the odd divisors.
Here is the final implementation.
bool isPrimeV5(int n) // 55{ if(n <= 1)return false;if(n!=2 && n%2==0)return false;int limit = sqrt(n); // sqrt(55) = 7 (only the integer part)for(int d=3; d<=limit; d+=2) // d <= 7, sqrt(n) * sqrt(n) = n > (7 * 7 = 49){if(n%d==0) // will run twice, when d is equal to 3, and 5 afterreturn false; // which it will return false}return true;}
The comparison of implementations
If we look at the two implementations, Implementation 1 and Implementation 3(v5), how can we see which implementation is better and how much better?
For better understanding, assume that $n=2^{31}1 = 2147483648$ (you may search this number, it’s the famous Mersenne prime number). How much time will the two implementations take?
As in Implementation 1 our loop runs for almost $n$ times, hence it runs $21474836482$ times,Whereas our Implementation 3(V5) runs only $\sqrt{2147483648}/2 = 46340/2=23170$ times. That means its almost $92681$ times faster than Implementation 1. We can also look at it another way. Let’s say we have a machine that runs our loop instruction 10,000 times in one second, then our Implementation 3(V5) will only take 2.3 seconds. But our Implementation 1 will take $213166.3$ seconds which is equivalent to $213166.3/(60 \times 60)=59$ hours approximately that is $2.5$ days.
This is a huge level of improvement in terms of efficiency.
We hope you appreciate this journey of improving these implementations and understanding why this entire journey of discovery and incremental improvement was worth it.
Exercise: Computing prime factorization
Write a program in the code editor below in such a way that it displays the prime factors of number n
. For example, the prime factors of 36 are 2 * 2 * 3 * 3.
#include <iostream> using namespace std; void allPrimeFactors(int n) { // 6 => 2 * 3 // Write code here. } int main() { int num; cout << "The number: "; cin >> num; cout << " "; allPrimeFactors(num); cout<< endl; return 0; }
Click “Show Solution” below to see the solution: