Recent Posts

Print prime number program in C++

Written by

Garvit Gulati

Understanding the problem

In the given question, we have to find and print all prime numbers between 1 and 100.

Any number is called a prime number if it has no factors other than one and the number itself. Rest of the numbers are called composite numbers. One is considered neither prime nor composite.

Examples of prime numbers:

2, 3, 5, 7, 13

Approaching the problem

To print all the prime numbers between 1 and 100 we would have to start from 2 (since 1 is neither prime nor composite) and then check for each number’s factors.

We will use a for loop from 2 to 100 to set the number to be checked.

Inside it, we will use another for loop from 2 to i to check for factors.

Note: The loop will run till i and not till i because if a number has no factors till i then it won’t have any factor. To prove this let’s presume a factor of i as j such that j>i  then there must be another factor i/j which will be smaller than i  since both the factors can’t be greater than i, therefore, if there are no factors of i less than i then the number doesn’t have any other factor.

Algorithm

  • Start a for loop from i = 2 to i = 100, which will set each number.
  • Initialize a variable ctr = 0 to count the number of factors.
  • Start a for loop from j = 2 to j = i to check for factors.
    • If i / j is equal to zero (hence j is a factor of i), then set ctr = 1 and break the loop.
  • Outside the loop, check if ctr is zero (hence the number has no factors and is a prime number), then print it.
  • Else, the number has at least one factor and is not a prime.

Code

#include <iostream>
#include<cmath>
using namespace std;

int main()
{
    cout << "Prime Numbers between 1 and 100 are:\n";

    for(int i = 2; i <= 100; ++i) //loop to check for each number in the range
    {
        int ctr = 0; //to maintain factor count

        for(int j = 2; j <= sqrt(i); ++j) //checking for factors
        {
            if(i % j == 0)
            {
                ctr = 1; //increasing factor count when found
            }
        }

        if(ctr == 0) //checking and printing prime numbers
        {
            cout << i << " ";
        }
    }

    return 0;
}

Output:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
Print prime number program in C++