Prime Number Program in C++ – [ Program with Explanation ]

 

Prime Number Algorithm:

1st Step: START.

2nd Step: Enter the number to Check for prime.

3rd Step: if the number is divisible by any other number and also divisible by itself then print “Number is Prime Number”.

4th Step: Else print “Number is not a Prime Number”.

5th Step: STOP.

1. Prime Number Program in C++

In this program, the compiler will ask the user to enter the number which user wants to check whether the number is prime or not. And after checking the compiler will print the output on the screen.

C++

1

#include <iostream>

2

using namespace std;

3

int main()

4

{

5

  int n, i;

6

  bool isPrime = true;

7

  cout << "Enter a positive integer: ";

8

  cin >> n;

9

  for(i = 2; i <= n / 2; ++i)

10

  {

11

      if(n % i == 0)

12

      {

13

          isPrime = false;

14

          break;

15

      }

16

  }

17

  if (isPrime)

18

      cout << "This is a prime number";

19

  else

20

      cout << "This is not a prime number";

21

  return 0;

22

}

Output:

Explanation:

let us consider n=5 for loop becomes for(i=1; i<5; i++)

1st Iteration: for(i=1; i<=5; i++) in 1st iteration i is incremented i.e the value of i for the next iteration is 2.If (n%i==0) then c is incremented i.e (5%1==0) then c is incremented.Here, (5%1=0) so c is incremented i.e c=1.

2nd Iteration: for(i=2;i<=5;i++) in 2nd iteration i is incremented i.e the value of i for the next iteration is 3.If (n%i==0) then c is incremented i.e (5%2==0) then c is incremented.here,(5%2!=0) so c is not incremented i.e c=1.

3rd Iteration: for(i=3;i<=5;i++) in 3nd iteration i is incremented i.e the value of i for the next iteration is 4.If (n%i==0) then c is incremented i.e (5%3==0) then c is incremented.Here,(5%3!=0) so c is not incremented i.e c=1.

4th Iteration: for(i=4;i<=5;i++) in 4th iteration i is incremented i.e the value of i for the next iteration is 5.If (n%i==0) then c is incremented i.e (5%4==0) then c is incremented.Here,(5%4!=0) so c is not incremented i.e c=1.

5th Iteration: for(i=5;i<=5;i++) in 5th iteration i is incremented i.e the value of i for the next iteration is 6.If (n%i==0) then c is incremented i.e (5%5==1) then c is incremented.Here,(5%5=0) so c is incremented i.e c=2.

6th Iteration: for(i=6;i<=5;i++) in 6th iteration the value of i is 6 which is greater than n i.e i>n(6>5) so the for loop is terminated.Here c=2 so the given number is prime number.

Time Complexity of This solution is O(n).

2. Program for Prime Number in C++ Using While Loop

In this program, we will use while loop instead of for loop. But, the logic behind the program in same.

C++

1

#include <iostream>

2

#include <math.h>

3

using namespace std;

4

int main()

5

{

6

    int num, i, f;

7

    //Reading a number from user

8

    cout<<"Enter any number:";

9

    cin>>num;

10

    f = 0;

11

    i = 2;

12

    while(i <= num/2)

13

    {

14

        if(num%i == 0)

15

        {

16

            f=1;

17

            break;

18

        }

19

        i++;

20

    }

21

    if(f == 0)

22

        cout<<num<<" is a Prime Number"<<endl;

23

    else

24

        cout<<num<<" is Not a Prime Number"<<endl;

25

   return 0;

26

}

Output:

3. Optimized School Method in C++

C++

1

#include <bits/stdc++.h> 

2

using namespace std; 

3

bool isPrime(int n) 

4

{ 

5

    // Corner cases 

6

    if (n <= 1) 

7

        return false; 

8

    if (n <= 3) 

9

        return true; 

10

    // This is checked so that we can skip 

11

    // middle five numbers in below loop 

12

    if (n % 2 == 0 || n % 3 == 0) 

13

        return false; 

14

    for (int i = 5; i * i <= n; i = i + 6) 

15

        if (n % i == 0 || n % (i + 2) == 0) 

16

            return false; 

17

    return true; 

18

} 

19

int main() 

20

{ 

21

    isPrime(11) ? cout << " true\n" : cout << " false\n"; 

22

    isPrime(15) ? cout << " true\n" : cout << " false\n"; 

23

    return 0; 

24

} 

25

​

Output:

4. C++ Program to Print Next Prime Number

In this program when the user enters any number to check whether it is prime or not then the compiler will print the next prime number occurs after the entered number by the user.

C++

1

#include<iostream>

2

#include<conio.h>

3

using namespace std;

4

int main()

5

{

6

  int i,j=2,num;

7

  cout<<"Enter any number: ";

8

  cin>>num;

9

  cout<<"Next prime number: ";

10

  for(i=num+1;i<3000;i++)

11

   {

12

    for(j=2;j<i;j++)

13

      {

14

     if(i %j==0)

15

     {

16

     break;

17

      } // if

18

     } // for

19

     if(i==j || i==1)

20

       {

21

       cout<<"\t"<<i;

22

    break;

23

    } // if

24

    }  // outer for

25

}

Output:

In the above program, we have entered the number as 5. And the compiler printed 7 as next prime number.

5. C++ Program to Print Prime Numbers from 1 to 100

In this program, we will print all the prime numbers between 1 and 100.

C++

1

#include <iostream>

2

using namespace std;

3

int isPrimeNumber(int);

4

int main()

5

{

6

   bool isPrime;

7

   for(int n = 2; n < 100; n++) {

8

      // isPrime will be true for prime numbers

9

      isPrime = isPrimeNumber(n);

10

      if(isPrime == true)

11

         cout<<n<<" ";

12

   }

13

   return 0;

14

}

15

// Function that checks whether n is prime or not

16

int isPrimeNumber(int n) {

17

   bool isPrime = true;

18

   for(int i = 2; i <= n/2; i++) {

19

      if (n%i == 0) {

20

         isPrime = false;

21

         break;

22

      }

23

   }  

24

   return isPrime;

25

}

Output:

6. C++ Program to print all Prime Numbers Between 1 to n

After Executing this program the compiler will ask the user to enter the number n to print all prime numbers between 1 to n. And then the compiler will start printing all the prime numbers.

C++

1

#include <iostream>

2

using namespace std;

3

int isPrimeNumber(int);

4

int main() {

5

   bool isPrime;

6

   int count;

7

   cout<<"Enter the value of n:";

8

   cin>>count;

9

   for(int n = 2; n < count; n++)

10

   {

11

       // isPrime will be true for prime numbers

12

       isPrime = isPrimeNumber(n);

13

       if(isPrime == true)

14

          cout<<n<<" ";

15

   }

16

   return 0;

17

}

18

// Function that checks whether n is prime or not

19

int isPrimeNumber(int n) {

20

   bool isPrime = true;

21

   for(int i = 2; i <= n/2; i++) {

22

      if (n%i == 0)

23

      {

24

         isPrime = false;

25

         break;

26

      }

27

   }

28

   return isPrime;

29

}

Output: