Skip to content

← Back to Overview

Prime Number Check

Concept Explanation

What is it?

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In simpler terms, a prime number can only be divided evenly by 1 and itself. Numbers that are not prime are called composite numbers. The number 1 is neither prime nor composite.

Why is it important?

Prime numbers are fundamental in number theory and have significant applications in computer science, especially in cryptography. Many encryption algorithms (like RSA) rely on the difficulty of factoring large numbers into their prime components. Understanding prime numbers is also a good exercise in applying loops and conditional logic.

Where is it used?

  • Cryptography: Secure communication, digital signatures, and public-key encryption.
  • Hashing: Some hashing algorithms use properties of prime numbers.
  • Random Number Generation: Often used in algorithms for generating pseudo-random numbers.
  • Algorithm Design: Prime numbers appear in various algorithms for tasks like factorization or number-theoretic computations.

Real-world example

Imagine a secret code where you need two very large, distinct prime numbers to create a key. The security of the code depends on how hard it is for someone else to find those two prime numbers by trying to divide your key. This is the basic principle behind RSA encryption, widely used for secure online transactions.

Algorithm

  1. Start.
  2. Get an integer num from the user.
  3. If num is less than or equal to 1, it is not prime.
  4. If num is 2, it is prime.
  5. If num is even (and greater than 2), it is not prime.
  6. For odd numbers greater than 2, iterate from 3 up to the square root of num (inclusive), incrementing by 2 in each step. a. If num is divisible by any of these numbers, it is not prime.
  7. If no divisors are found, the number is prime.
  8. Display the result.
  9. End.

Optimization Note: We only need to check for divisors up to the square root of num. If a number n has a divisor d greater than sqrt(n), then it must also have a divisor n/d that is less than sqrt(n).

Edge Cases: - Inputting non-integer values (handled by language-specific error mechanisms or explicit validation). - num = 0 or num = 1: These are specifically defined as not prime. - num = 2: The only even prime number.

Implementations

import java.util.Scanner;

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

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

        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(num + " is a PRIME number.");
        } else {
            System.out.println(num + " is NOT a PRIME number.");
        }

        scanner.close();
    }
}

import math

# Get a number from the user
num_str = input("Enter a number: ")
num = int(num_str)

print(f"Input Number: {num}")

is_prime = True

if num <= 1:
    is_prime = False
else:
    # Check for factors from 2 to sqrt(num)
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            is_prime = False
            break

if is_prime:
    print(f"{num} is a PRIME number.")
else:
    print(f"{num} is NOT a PRIME number.")

#include <stdio.h>
#include <math.h> // For sqrt()

int main() {
    int num, i, is_prime = 1;

    printf("Enter a positive integer: ");
    scanf("%d", &num);

    printf("Input Number: %d\n", num);

    if (num <= 1) {
        is_prime = 0;  // 1 is not prime, but handle as special case
    } else {
        // Check for factors from 2 to sqrt(num)
        for (i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) {
                is_prime = 0;  // Found a factor, not prime
                break;
            }
        }
    }

    if (is_prime == 1) {
        printf("%d is a PRIME number.\n", num);
    } else {
        printf("%d is NOT a PRIME number.\n", num);
    }

    return 0;
}

SET SERVEROUTPUT ON;
DECLARE
  input_num   NUMBER := &Enter_an_Integer;
  is_prime    BOOLEAN := FALSE;  // Start assuming number is not prime
BEGIN
  DBMS_OUTPUT.PUT_LINE('Input Number: ' || input_num);

  IF input_num <= 1 THEN
    is_prime := FALSE;  // 1 is not considered prime
  ELSE
    // Check for factors from 2 to sqrt(num)
    FOR i IN 2..TRUNC(SQRT(input_num)) LOOP
      IF MOD(input_num, i) = 0 THEN
        is_prime := FALSE;  // Found a factor, not prime
        EXIT;
      END IF;
    END LOOP;
  END IF;

  IF is_prime THEN
    DBMS_OUTPUT.PUT_LINE(input_num || ' is a PRIME number.');
  ELSE
    DBMS_OUTPUT.PUT_LINE(input_num || ' is NOT a PRIME number.');
  END IF;
END;
/

Explanation

  • Java: Uses a for loop to check for divisibility up to the square root of the number. The Math.sqrt() method is used.
  • Python: Also uses a for loop and math.sqrt(). The range() function and int() conversion are key for loop iteration.
  • C: Employs a for loop with sqrt() from math.h. The is_prime flag is an integer (1 for true, 0 for false).
  • Oracle: Implemented in PL/SQL. Uses a FOR loop from 2 up to the truncated square root of the input number. The MOD() function checks for divisibility. SQRT() function is available.

Complexity Analysis

  • Time Complexity: O(sqrt(n)) - The loop runs up to the square root of the input number.
  • Space Complexity: O(1) - A fixed number of variables are used.

Flowchart

graph TD
    A[Start] --> B[Get Integer num]
    B --> C{num <= 1?}
    C -- Yes --> D[is_prime = FALSE]
    C -- No --> E[is_prime = TRUE]
    E --> F[i = 2 to sqrt(num)]
    F --> G{num % i == 0?}
    G -- Yes --> H[is_prime = FALSE]
    H --> I[Break Loop]
    G -- No --> J[i++]
    J --> F
    I --> K{is_prime == TRUE?}
    K -- Yes --> L[Display PRIME]
    K -- No --> M[Display NOT PRIME]
    L --> N[End]
    M --> N
    D --> N

Sample Dry Run

Step num i is_prime num % i Description
Input 7 - true - User enters 7
num <= 1? 7 - true - False (7 > 1)
Loop i=2 7 2 true 1 7 % 2 != 0
Loop i=3 7 3 true 1 7 % 3 != 0
Loop End - - true - Loop finishes (sqrt(7) is approx 2.64)
is_prime? - - true - True
Output - - - - Display "7 is a PRIME number."
End - - - - Program terminates
Input 10 - true - User enters 10
num <= 1? 10 - true - False (10 > 1)
Loop i=2 10 2 true 0 10 % 2 == 0
is_prime - - false - Set is_prime to false, break loop
is_prime? - - false - False
Output - - - - Display "10 is NOT a PRIME number."
End - - - - Program terminates

Practice Problems

Easy

  • Modify the program to find prime numbers within a given range (e.g., 1 to 100).
  • Optimize the prime checking algorithm further (e.g., check only up to 5, then multiples of 6 ± 1).

Medium

  • Implement a program to find the prime factors of a given number.
  • Write a program to display the first N prime numbers.

Hard

  • Implement the Sieve of Eratosthenes to efficiently find all prime numbers up to a specified limit.
  • Explore primality tests for very large numbers (e.g., Miller-Rabin test).

"The only source of knowledge is experience." - Albert Einstein