Find smallest prime divisor of a number in C++

Hi there. Today we are going to see how to get the smallest prime divisor of any number using C++. But what if you want to implement this in C? You can do that by replacing input and output streams of C++ with C. After that, change the library at the beginning, and you will get the program in C.

Now, let’s see how the program works. This program can be implemented using various methods, but I chose the most beginner-friendly method, so that you can understand it easily. Once you get comfortable with this method,  you can try to implement it in a more efficient way.

Program description

We can divide this problem into two sub-problems. First, we need to calculate the divisors of the given number. And for each divisor, proceeding in ascending order, we can check if it is prime or not. If one of them is prime, that will be our answer.

First, we will have a function, which tells us if a given number is prime or not. It will return true if the number is prime, or false if it isn’t. Then, for any given number, we have to proceed in ascending order, from 2 till that number, until we find a divisor.  And for each divisor, we will use our prime check function, to check if it is prime or not. The first divisor which is prime will be the answer. This will be done in the main method.

Let’s proceed to the programming part.

#include<bits/stdc++.h>
using namespace std;

bool prime_check(int n)
{
  for(int i=2;i<=n/2;i++)
  {
    if(n%i==0)
    {
      return false;
      break;
    }
  }
  return true;
}

int main()
{
	int n;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		if(n%i==0 & prime_check(i)==true)
		{
			cout<<i;
			break;
		}
	}
	return 0;
}

The output will give us the smallest prime divisor of input. If the input is prime, that itself will get printed. The “if” statement checks for prime and divisibility both, and our answer gets printed out.

Now let’s see the output. First, we will take input as 34.

2

34 has two prime divisors. 17 and 2. And the smallest one gets printed out.
Let’s see another example. We will take 41 this time, which is a prime number itself.

41

The input is prime. Therefore, input itself will be the answer.

So we are able to find the smallest prime divisor of a number with C++ program.

I hope you found the article useful. And for your own exercise, try implementing this program in a more efficient way. I am sure you will find something interesting.

Also, read: Generation of pseudo-random numbers with C++

2 responses to “Find smallest prime divisor of a number in C++”

  1. arth says:

    Smallest divisor exclude 1 is always prime. No need to «check» it.
    For prime n, your loop will fully exhausted, while only need to check i of [2..sqrt(n)].
    Better: if we check 2 as divisor early, we can check starting from 3 with step 2.

    So, correct and efficient algorithm is:

    if(n%2==0) return 2;
    for(int i=3; i*i<=n; ++i) if(n%i == 0) return i;
    return n;

  2. arth says:

    Sure, I was mean i+=2 in the for loop:

    “`
    if(n%2==0) return 2;
    for(int i=3; i*i<=n; i+=2) if(n%i == 0) return i;
    return n;
    “`

Leave a Reply