Prime Number Program In C++ : 3 Awesome Ways

Prime numbers are numbers greater than 1 that has only two factors 1 and itself. A prime number can’t be divided by any other positive number . For eg the number 13. The only divisors it has are 1 and 13. On the other hand, 15 isn’t a prime because it can divided by 5, 3 apart from itself and 1.

In this article we will discuss various methods to check if number is prime or not, along with it we will learn to write prime number program in c++.number program in c++.

FAQ’s About Prime Numbers

Prime Number Program In C++.

Given a positive integer, check if the number is prime or not. Write prime number program in c++ that takes integer as input and return true or false as output.

Input:  n = 13
Output: true
Input:  n = 27
Output: false
Input:  n = 1
Output: false

Solution 1: Naive Approach

Algorithm

One Naive method is to check by dividing n with all the numbers from 2 to n-1. If we find any number that divides, we return false else true.

Implementation:

// Prime Number Program In C++

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n) {
  // Handling Edge Case
  if (n <= 1) {
    return false;
  }

  // Iterate from 2 to n-1 and check if any number divides n
  for (int i = 2; i < n; i++) {
    if (n % i == 0) {
      return false;
    }
  }
  // If not return true
  return true;
}

int main() {
  isPrime(11) ? cout << " is prime\n" : cout << " not prime\n";
  isPrime(15) ? cout << " is prime\n" : cout << " not prime\n";
  return 0;
}

Complexity:

Since we are iterating from 2 to n-1. Complexity for above prime number program in c++ is O(n).

Solution 2 : Optimised

Instead of checking till n, we can check till √n because a larger factor of n must be a multiple of smaller factor that has been already checked.

How does it work?

Let’s suppose that the given integer N is not prime. Then N can be factorised into two factors let’s say p and q ,  such that 2<= p,q < N and  N = a*b.

It can be clearly seen that both of them can’t be greater than √n simultaneously. Therefore there will be surely, one integer (let’s assume p) which is smaller than √n and divides n if n is not prime number

Now, if you could not find any divisor of N belonging in the range 2 to √n, what does that mean? This means that N does not have any divisor between 2 to p  as p <= √n,. Therefore, p = 1 and q = n and hence by definition, N is prime.

Let’s look into prime number program in C++.

Implementation

// Prime Number Program In C++

#include <bits/stdc++.h>


using namespace std;

bool isPrime(int n) {
  // Handling Edge Case
  if (n <= 1) {
    return false;
  }

  // Iterate from 2 to sqrt(n) and check if any number divides n
  for (int i = 2; i < sqrt(n); i++) {
    if (n % i == 0) {
      return false;
    }
  }
  // If not return true
  return true;
}

int main() {
  isPrime(11) ? cout << " is prime\n" : cout << " not prime\n";
  isPrime(15) ? cout << " is prime\n" : cout << " not prime\n";
  return 0;
}

Complexity

Since we are iterating from 2 to sqrt(n). Complexity is O(√n).

Solution 3 : Primality test

We can further improve this technique. On observing we can see that all primes larger than 3 are in their form of 6?±1. where “k” is any number higher than 0. This is because all numbers can be expressed in terms of (6 k + i) in which i is 0, 1 2, 3, 4 or 5

If a number leaves a remainder of 0, 2 or 4 when divided by 6, then it is even and therefore non-prime (unless it is 2). If it leaves a remainder of 3 when divided by 6 then it is divisible by 3 and therefore non-prime (unless it is 3). That leaves just the remainders 1 and 5, or in other words, numbers of the form 6?±1.

So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1

Let’s see how can we implement this for prime number program in C++.

Implementation

// Prime Number Program In C++

#include <bits/stdc++.h>

using namespace std;

bool isPrime(int n) {
  // Edge cases
  if (n <= 1)
    return false;
  if (n <= 3)
    return true;

  if (n % 2 == 0 || n % 3 == 0)
    return false;

  // Since number is not divisible by 2 or 3 we can skip even numbers 
  // and those multiple of 3
  // i.e checking only numbers of form 6k-1 or 6k+1;
  for (int i = 5; i * i <= n; i = i + 6) {

    if (n % i == 0 || n % (i + 2) == 0) {
      return false;
    }
  }

  return true;
}

int main() {
  isPrime(11) ? cout << " is prime\n" : cout << " not prime\n";
  isPrime(15) ? cout << " is prime\n" : cout << " not prime\n";
  return 0;
}

There is yet another advance way we can check if number is prime or not. The algorithm is called Sieve of Eratosthenes.

Conclusion

In this article we discussed what prime numbers are and various methods to check if number is prime or not along with prime number program in c++.

Got a question or just want to chat? Comment below or drop by our forums, where a bunch of the friendliest people you’ll ever run into will be happy to help you out!