Understanding Prime Numbers Using Loop in Programming

Introduction

Prime numbers are one of the most important concepts in mathematics and programming. They are widely used in algorithms, cryptography, and problem-solving. In this blog, we will learn what a prime number is and how to write a program using loops to check whether a number is prime.

---

What is a Prime Number?

A prime number is a number that is divisible only by:

• 1
• Itself

Examples:

• 2, 3, 5, 7, 11 → Prime numbers

Non-Prime Numbers:

• 4 (divisible by 2)
• 6 (divisible by 2 and 3)

---

Logic Behind Prime Number Program

To check if a number is prime:

1. Take a number as input
2. Check divisibility from 2 to n-1
3. If any number divides it → Not Prime
4. If no number divides it → Prime

---

Java Program Using Loop

import java.util.Scanner;

public class PrimeNumber {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.print("Enter a number: ");
        int num = sc.nextInt();
        int count = 0;

        for(int i = 1; i <= num; i++) {
            if(num % i == 0) {
                count++;
            }
        }

        if(count == 2) {
            System.out.println("Prime Number");
        } else {
            System.out.println("Not a Prime Number");
        }
    }
}

---

Optimized Approach (Better Logic)

Instead of checking till n, we can check till √n (square root of n) to improve performance.

public class PrimeOptimized {
    public static void main(String[] args) {
        int num = 29;
        boolean isPrime = true;

        if(num <= 1) {
            isPrime = false;
        } else {
            for(int i = 2; i <= Math.sqrt(num); i++) {
                if(num % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

        if(isPrime) {
            System.out.println("Prime Number");
        } else {
            System.out.println("Not Prime");
        }
    }
}

---

Why Optimization Matters?

• Reduces number of iterations
• Improves performance for large numbers
• Used in real-world applications

---

Time Complexity

• Basic approach → O(n)
• Optimized approach → O(√n)

---

Conclusion

Prime numbers are fundamental in programming and problem-solving. By using loops, we can easily determine whether a number is prime. Optimizing the solution using square root logic makes the program faster and more efficient.

---

Tip

Always try to optimize your logic when working with loops to improve performance in real-world applications.

---