Print prime number program in C++

Understanding Prime Numbers

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. The number 1 is neither prime nor composite.

Examples of prime numbers:

2, 3, 5, 7, 11, 13

Solution Approach

To find all prime numbers between 1 and 100:

1. Start checking from 2 (the first prime number)

2. For each number i from 2 to 100:

   - Check for divisors from 2 up to √i

   - If no divisors found, the number is prime

Key Insight:

We only need to check divisors up to √i because:

• If i has a factor greater than √i, it must have a corresponding factor smaller than √i

• This optimization significantly reduces the number of checks needed

Algorithm

1. Initialize outer loop from i = 2 to i = 100

2. For each i:

   - Set counter ctr = 0

   - Inner loop from j = 2 to j ≤ √i:

     - If i % j == 0, set ctr = 1 and break

3. After inner loop:

   - If ctr == 0, print i (prime number)

   - Else, continue to next number

Implementation

#include <iostream>

#include <cmath>

using namespace std;

int main() {

    cout << "Prime numbers between 1 and 100:\n";

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

        bool isPrime = true;

        for(int j = 2; j <= sqrt(i); ++j) {

            if(i % j == 0) {

                isPrime = false;

                break;

            }

        }

        if(isPrime) {

            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

Improvements Made

1. Variable Naming: Changed ctr to more descriptive isPrime boolean

2. Optimization: Used sqrt(i) as the upper bound for divisor checking

3. Readability: Improved code formatting and comments

4. Output Format: Cleaned up the output presentation

5. Explanation: Clarified the mathematical reasoning behind checking up to √i

Time Complexity

The algorithm has a time complexity of O(n√n), which is efficient for the given range (1 to 100). For larger ranges, more sophisticated algorithms like the Sieve of Eratosthenes would be more efficient.