Problem Solving: Composites, Primes and Prime Factorization

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 n-1 (not checking with the number itself and 1).

If the number n is divisible by at least one number from 2 to number n-1, 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.

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:

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.

Let’s add this function and run our complete program:

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:

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.

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.

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 by 2, 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.

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 divide n. 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.

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:

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.

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.

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 $2147483648-2$ 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.

Click “Show Solution” below to see the solution: