Primes in Range

Program to find all prime numbers in a given range

IntermediateTopic: Loop Programs

C++ Primes in Range Program

This program helps you to learn the fundamental structure and syntax of C++ programming.

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

bool isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int start, end;
    
    cout << "Enter start of range: ";
    cin >> start;
    
    cout << "Enter end of range: ";
    cin >> end;
    
    cout << "Prime numbers between " << start << " and " << end << " are: ";
    
    for (int i = start; i <= end; i++) {
        if (isPrime(i)) {
            cout << i << " ";
        }
    }
    cout << endl;
    
    return 0;
}

Output

Enter start of range: 10
Enter end of range: 30
Prime numbers between 10 and 30 are: 11 13 17 19 23 29

Understanding Primes in Range

This program finds all prime numbers within a given range. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This program demonstrates function creation, nested loops, mathematical optimization, and efficient prime checking algorithms.

---

1. What is a Prime Number?

A prime number is a natural number greater than 1 that:

•Is divisible only by 1 and itself

•Has exactly two distinct positive divisors

Examples of prime numbers:

•2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, ...

Examples of non-prime (composite) numbers:

•4 (divisible by 1, 2, 4)

•6 (divisible by 1, 2, 3, 6)

•8 (divisible by 1, 2, 4, 8)

•9 (divisible by 1, 3, 9)

Special cases:

•1 is NOT prime (only one divisor)

•2 is the only even prime number

•All other even numbers (>2) are composite

Applications:

•Cryptography (RSA encryption)

•Hash functions

•Random number generation

•Mathematical research

---

2. Header Files Used

#include <iostream>

•Provides cout for output and cin for input

#include <cmath>

•Provides sqrt() function

•Used for the square root optimization in prime checking

---

3. The isPrime() Helper Function

bool isPrime(int n) {

if (n <= 1) return false;

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

if (n % i == 0) return false;

}

    return true;

Why use a helper function?

•Separates prime-checking logic from main program

•Makes code more readable and reusable

•Can be called multiple times easily

Function breakdown:

Step 1: Check for edge cases

if (n <= 1) return false;

•Numbers ≤ 1 are not prime

•Returns false immediately for invalid inputs

Step 2: Check divisibility from 2 to √n

for (int i = 2; i <= sqrt(n); i++)

•We only need to check up to the square root of n

•This is the

key optimization

Why check only up to √n?

•If n has a divisor greater than √n, it must also have a divisor less than √n

•Example: For n = 36

•Divisors: 1, 2, 3, 4, 6, 9, 12, 18, 36

•√36 = 6

•If we find 2, 3, 4, or 6 divides 36, we don't need to check 9, 12, 18

•They are just the "other half" of the factor pairs

Step 3: Check if i divides n

if (n % i == 0) return false;

•If any number from 2 to √n divides n, n is not prime

•Return false immediately

Step 4: If no divisors found

return true;

•If the loop completes without finding any divisors, n is prime

---

4. Understanding the Square Root Optimization

Naive approach (checking all numbers from 2 to n-1):

•For n = 100: Check 2, 3, 4, ..., 99 (98 checks)

•Time complexity: O(n)

Optimized approach (checking up to √n):

•For n = 100: Check 2, 3, 4, ..., 10 (9 checks)

•Time complexity: O(√n)

Much faster!

Example: Checking if 97 is prime

Naive:

Check 2, 3, 4, 5, ..., 96 (95 checks)

Optimized:

Check 2, 3, 4, 5, 6, 7, 8, 9, 10 (9 checks)

•√97 ≈ 9.85

•We check up to 9

•Since none divide 97, it's prime ✅

---

5. Main Function - Declaring Variables

int start, end;

•start → beginning of the range

•end → end of the range

Example:

•User enters: start = 10, end = 30

•We'll check all numbers from 10 to 30 for primality

---

6. Taking Input From User

`cout << "Enter start of range: ";`

cin >> start;

`cout << "Enter end of range: ";`

cin >> end;

•Prompts user for range boundaries

•Reads and stores them

Example:

•User enters:

10

and

30

•start = 10, end = 30

---

7. Displaying Range Header

`cout << "Prime numbers between " << start << " and " << end << " are: ";`

This prints:

•Text: "Prime numbers between "

•Start value: 10

•Text: " and "

•End value: 30

•Text: " are: "

Output:

Prime numbers between 10 and 30 are:

---

8. Iterating Through the Range

for (int i = start; i <= end; i++)

This loop goes through each number in the range:

•Starts from start (10)

•Continues while i <= end (30)

•Increments i by 1 each iteration

Iterations:

•i = 10, 11, 12, 13, ..., 29, 30

---

9. Checking and Printing Prime Numbers

if (isPrime(i))

cout << i << " ";

For each number in the range:

•Call isPrime(i) to check if it's prime

•If isPrime(i) returns true, print the number

•Print a space after each prime for readability

Step-by-step execution (range 10-30):

i = 10:

•isPrime(10) → checks 2, 3, ... up to √10 ≈ 3

•10 % 2 == 0 →

not prime

❌

i = 11:

•isPrime(11) → checks 2, 3, ... up to √11 ≈ 3

•None divide 11 →

prime

✅ → Print "11 "

i = 12:

•12 % 2 == 0 →

not prime

❌

i = 13:

•None divide 13 →

prime

✅ → Print "13 "

... and so on ...

Final output:

"11 13 17 19 23 29 "

•26: Divisible by 2, 13 →

Not prime

•27: Divisible by 3, 9 →

Not prime

•28: Divisible by 2, 4, 7, 14 →

Not prime

•29: No divisors →

Prime

✅

•30: Divisible by 2, 3, 5, 6, 10, 15 →

Not prime

Result:

11, 13, 17, 19, 23, 29

---

11. Why This Approach is Efficient

For range 10 to 30:

•We check 21 numbers (10 to 30)

•For each number, we check up to √n divisors

•Maximum checks per number: √30 ≈ 5

•Total operations: ~21 × 5 = 105 operations

Alternative (naive prime checking):

•Check all numbers from 2 to n-1 for each number

•For number 30: Check 2, 3, 4, ..., 29 (28 checks)

•Total operations: Much higher!

Our approach is much faster, especially for larger ranges.

---

12. Further Optimizations (Advanced)

Sieve of Eratosthenes:

•For finding many primes, sieve is even faster

•Marks multiples of primes as composite

•Time complexity: O(n log log n)

•Better for finding all primes up to n

Our approach is good for:

•Checking individual numbers

•Small to medium ranges

•When you need to check specific numbers

---

13. Edge Cases

Case 1: Range includes 1 or 0

•isPrime(1) returns false (handled in function)

•isPrime(0) returns false

Case 2: Range includes 2

•2 is prime (only even prime)

•Handled correctly

Case 3: start > end

•Loop won't execute

•Output: "Prime numbers between X and Y are: " (empty)

Case 4: Negative numbers

•isPrime() returns false for n <= 1

•Handled correctly

---

Summary

•Prime number has exactly two divisors: 1 and itself

•Helper function isPrime() checks if a number is prime

•Square root optimization: only check divisors up to √n

•Iterate through range, check each number, print primes

•This approach is efficient for small to medium ranges

•Understanding prime checking is fundamental in number theory

This program teaches:

•Function creation and usage

•Mathematical optimization (square root trick)

•Nested logic (loop calling function)

•Efficient algorithm design

•Number theory concepts

Mastering prime number algorithms helps in:

•Cryptography and security

•Competitive programming

•Mathematical problem solving

•Many real-world applications

Prime numbers are fundamental in mathematics and computer science, and understanding how to efficiently check for them is a crucial programming skill.

Let us now understand every line and the components of the above program.

Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.

Practical Learning Notes for Primes in Range

This C++ program is part of the "Loop Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.

A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.

For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.

Armstrong Number

Prime Check

Armstrong Number