← Back to Lab HomeLab Exercise – 04

Experiment 4 – Prime Number Check

Aim

To check whether a given number is prime or not using loops and conditional statements. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This experiment helps students understand efficient algorithm design, loop optimization, and mathematical problem-solving in programming.

Through this experiment, students will learn to implement prime checking algorithms, understand optimization techniques (checking up to sqrt(n)), and handle edge cases in mathematical computations.

Learning Outcomes

After completing this experiment, students will be able to:

  • Understand the mathematical definition of prime numbers
  • Implement prime checking algorithms using loops and conditions
  • Apply optimization techniques (checking up to sqrt(n) instead of n/2)
  • Handle edge cases (numbers less than 2, even numbers, etc.)
  • Use break statement to exit loops early when divisor is found
  • Write efficient code by reducing unnecessary iterations
  • Understand the importance of algorithm optimization
  • Apply mathematical concepts in programming solutions

Algorithm

The algorithm to check if a number is prime involves testing divisibility by numbers from 2 to sqrt(n):

Algorithm Steps:

  1. Start: Begin program execution
  2. Input: Read a positive integer n from the user
  3. Check Base Cases:
    • If n < 2, it's not prime (return false)
    • If n == 2, it's prime (return true)
    • If n is even and n > 2, it's not prime
  4. Check Odd Divisors: For odd numbers greater than 2
    • Initialize flag = 0 (0 means prime, 1 means composite)
    • Loop from i = 3 to sqrt(n), increment by 2 (only check odd numbers)
    • If n % i == 0, set flag = 1 and break
  5. Determine Result:
    • If flag == 0, number is prime
    • If flag == 1, number is composite (not prime)
  6. Output: Display whether the number is prime or not
  7. Stop: End program execution

Optimization Note: We only check up to sqrt(n) because if n has a divisor greater than sqrt(n), it must also have a corresponding divisor less than sqrt(n). Checking only odd numbers (after verifying it's not even) further optimizes the algorithm.

Procedure

  1. Include stdio.h and optionally math.h for sqrt function
  2. Declare variables: n (number to check) and flag (0 for prime, 1 for composite)
  3. Read the number from user
  4. Check if number is less than 2 (not prime)
  5. Check if number is 2 (prime)
  6. For numbers greater than 2, check divisibility:
    • Loop from 2 to sqrt(n) or n/2
    • If n is divisible by any number, set flag = 1 and break
    • If no divisor found, number is prime
  7. Display result based on flag value

Flowchart

START
  │
  ├─→ Declare variables: n, i, flag = 0
  │
  ├─→ Read n
  │
  ├─→ IF (n < 2)
  │   │
  │   └─→ Display "Not a prime number"
  │   └─→ END
  │
  ├─→ IF (n == 2)
  │   │
  │   └─→ Display "Prime number"
  │   └─→ END
  │
  ├─→ FOR i = 2 to sqrt(n)
  │   │
  │   ├─→ IF (n % i == 0)
  │   │   │
  │   │   ├─→ flag = 1
  │   │   └─→ BREAK
  │   │
  │   └─→ END FOR
  │
  ├─→ IF (flag == 0)
  │   │
  │   └─→ Display "Prime number"
  │
  ├─→ ELSE
  │   │
  │   └─→ Display "Not a prime number"
  │
  └─→ END

Program Code

#include <stdio.h>
#include <math.h>

int main() {
    int n, i, flag = 0;
    
    // Input number
    printf("Enter a positive integer: ");
    scanf("%d", &n);
    
    // Check for numbers less than 2
    if (n < 2) {
        printf("%d is not a prime number.\n", n);
        return 0;
    }
    
    // 2 is the only even prime number
    if (n == 2) {
        printf("%d is a prime number.\n", n);
        return 0;
    }
    
    // Check for even numbers (except 2)
    if (n % 2 == 0) {
        printf("%d is not a prime number.\n", n);
        return 0;
    }
    
    // Check divisibility from 3 to sqrt(n), step by 2
    for (i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            flag = 1;
            break;
        }
    }
    
    // Display result
    if (flag == 0) {
        printf("%d is a prime number.\n", n);
    } else {
        printf("%d is not a prime number.\n", n);
    }
    
    return 0;
}

// Simpler version without math.h:
/*
for (i = 2; i <= n/2; i++) {
    if (n % i == 0) {
        flag = 1;
        break;
    }
}
*/

Sample Input and Output

Sample 1:

Input:

Enter a positive integer: 17

Output:

17 is a prime number.

Sample 2:

Input:

Enter a positive integer: 15

Output:

15 is not a prime number.

(15 = 3 × 5)

Sample 3:

Input:

Enter a positive integer: 1

Output:

1 is not a prime number.

Sample 4:

Input:

Enter a positive integer: 29

Output:

29 is a prime number.

Use Case / Real-world Relevance

Prime numbers are fundamental in mathematics and have critical applications:

  • Cryptography: RSA encryption relies on large prime numbers for security
  • Hash Functions: Prime numbers are used in hash table implementations for better distribution
  • Random Number Generation: Prime numbers are used in pseudo-random number generators
  • Error Detection: Checksums and error-correcting codes use prime numbers
  • Computer Science: Prime numbers help in designing efficient algorithms and data structures
  • Mathematics: Fundamental in number theory, used in factorization and modular arithmetic
  • Security Systems: Prime numbers are essential in digital signatures and secure communications
  • Game Development: Used in procedural generation and randomization algorithms

Understanding prime number algorithms helps in learning optimization techniques, as efficient prime checking requires careful loop design and mathematical insights. Prime numbers are fundamental in computer science, especially in security and cryptography applications where large primes are essential for encryption algorithms.

Viva Questions

Q1: What is a prime number? Give examples.

A prime number is a natural number greater than 1 that has exactly two distinct positive divisors: 1 and itself. Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Note that 1 is not considered prime because it has only one divisor.

Q2: Why do we check only up to sqrt(n) instead of n/2 or n-1?

If n has a divisor greater than sqrt(n), it must have a corresponding divisor less than sqrt(n). For example, if 100 has divisor 20, it also has 5 (since 20 × 5 = 100). Checking up to sqrt(n) is sufficient and more efficient. This reduces time complexity from O(n) to O(√n).

Q3: Why do we check if the number is even before the loop?

All even numbers greater than 2 are composite (divisible by 2). By checking this first, we can immediately determine they're not prime without entering the loop, saving computation. The only even prime number is 2, which we handle as a special case.

Q4: What is the time complexity of the prime checking algorithm?

The optimized algorithm has time complexity O(√n) because we check divisors only up to sqrt(n). The naive approach checking up to n-1 would be O(n). For very large numbers, more advanced algorithms like the Sieve of Eratosthenes or probabilistic tests are used.

Q5: Can we use a while loop instead of for loop? Show how.

Yes: int i = 3; while (i <= sqrt(n)) { if (n % i == 0) { flag = 1; break; } i += 2; }. Both loops are equivalent. The for loop is more concise, while the while loop gives more explicit control over the increment.

Q6: What happens if we don't use the break statement?

Without break, the loop continues checking all divisors even after finding one, which is inefficient but still correct. The break statement optimizes the algorithm by stopping as soon as we find a divisor, since we only need to know if any divisor exists, not find all divisors.

Q7: Why is 2 a special case in prime checking?

2 is the only even prime number. All other even numbers are divisible by 2, making them composite. We handle 2 as a special case because our optimization skips even numbers in the loop. Without this check, 2 would incorrectly be identified as composite.

Q8: How would you modify the program to find all prime numbers up to N?

Use nested loops: outer loop from 2 to N, inner loop checks if each number is prime. More efficiently, use the Sieve of Eratosthenes algorithm which marks multiples of primes, eliminating the need to check each number individually. This reduces complexity significantly for finding multiple primes.

Related Links

🔹 Author: Dr. J. Siva Ramakrishna

🔹 Institution: Narayana Engineering College, Gudur

🔹 Last Updated: 9 January 2026

← Previous: Experiment 3Next: Experiment 5→