Day 10: Prime Numbers

Objective

Today, you will create a program to check if a number is prime. Prime numbers are an essential concept in mathematics and are often used in cryptography, algorithms, and data security.

A prime number is any number greater than 1 that is only divisible by 1 and itself. For example:

  • Prime Numbers: 2, 3, 5, 7, 11, 13, 17
  • Non-Prime Numbers: 4, 6, 8, 9, 12 (these are divisible by numbers other than 1 and themselves).

Why This Challenge Is Important

By solving this challenge, you will:

  1. Strengthen Your Understanding of Loops and Conditions: Use loops to check divisibility and conditions to determine primality.
  2. Practice Optimization: Learn how to minimize the number of iterations required to check if a number is prime.
  3. Build Problem-Solving Skills: Tackle edge cases like 1 and negative numbers.

Steps to Solve

1. Understand the Logic for Primality

To determine if a number n is prime:

  1. A number less than or equal to 1 is not prime.
  2. A number is prime if it has no divisors other than 1 and itself.
  3. Check divisors from 2 up to sqrt{n}​:
    • If n%i==0, n is not prime because it is divisible by i.

Code Examples

Python Example

Basic Version:

# Get input from the user

number = int(input("Enter a number: "))

# Check if the number is prime
if number <= 1:
    print(f"{number} is not a prime number.")
else:
    is_prime = True
    for i in range(2, number):  # Check divisors from 2 to number-1
        if number % i == 0:
            is_prime = False
            break

    if is_prime:
        print(f"{number} is a prime number.")
    else:
        print(f"{number} is not a prime number.")

Optimized Version:

import math

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

# Check if the number is prime
if number <= 1:
    print(f"{number} is not a prime number.")
else:
    is_prime = True
    for i in range(2, int(math.sqrt(number)) + 1):  # Only check up to the square root of the number
        if number % i == 0:
            is_prime = False
            break

    if is_prime:
        print(f"{number} is a prime number.")
    else:
        print(f"{number} is not a prime number.")

Java Example

Basic Version:

import java.util.Scanner;

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

        // Get input from the user
        System.out.print("Enter a number: ");
        int number = scanner.nextInt();

        if (number <= 1) {
            System.out.println(number + " is not a prime number.");
        } else {
            boolean isPrime = true;
            for (int i = 2; i < number; i++) { // Check divisors from 2 to number-1
                if (number % i == 0) {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                System.out.println(number + " is a prime number.");
            } else {
                System.out.println(number + " is not a prime number.");
            }
        }
    }
}

Optimized Version:

import java.util.Scanner;

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

        // Get input from the user
        System.out.print("Enter a number: ");
        int number = scanner.nextInt();

        if (number <= 1) {
            System.out.println(number + " is not a prime number.");
        } else {
            boolean isPrime = true;
            for (int i = 2; i <= Math.sqrt(number); i++) { // Only check up to the square root
                if (number % i == 0) {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime) {
                System.out.println(number + " is a prime number.");
            } else {
                System.out.println(number + " is not a prime number.");
            }
        }
    }
}

JavaScript Example

Basic Version:

// Get input from the user
let number = parseInt(prompt("Enter a number:"));

if (number <= 1) {
    console.log(`${number} is not a prime number.`);
} else {
    let isPrime = true;
    for (let i = 2; i < number; i++) { // Check divisors from 2 to number-1
        if (number % i === 0) {
            isPrime = false;
            break;
        }
    }

    if (isPrime) {
        console.log(`${number} is a prime number.`);
    } else {
        console.log(`${number} is not a prime number.`);
    }
}

Optimized Version:

// Get input from the user
let number = parseInt(prompt("Enter a number:"));

if (number <= 1) {
    console.log(`${number} is not a prime number.`);
} else {
    let isPrime = true;
    for (let i = 2; i <= Math.sqrt(number); i++) { // Only check up to the square root
        if (number % i === 0) {
            isPrime = false;
            break;
        }
    }

    if (isPrime) {
        console.log(`${number} is a prime number.`);
    } else {
        console.log(`${number} is not a prime number.`);
    }
}

Edge Cases to Consider

  1. Negative Numbers: Prime numbers are greater than 1. Handle inputs like -5 appropriately.
  2. Numbers 0 and 1: Neither is prime.
  3. Large Numbers: Ensure your program is efficient for larger inputs by using the optimized approach.

Extensions to Explore

  1. Prime List: Modify the program to print all prime numbers up to a user-provided limit.
  2. Prime Count: Count the number of primes between two numbers.
  3. Twin Primes: Check if two consecutive numbers are both prime.

What You’ve Learned

  • How to determine if a number is divisible using the modulus operator.
  • How to optimize a solution by reducing the number of iterations.
  • How to handle edge cases like small or negative numbers.

This task builds a solid foundation for working with numbers and understanding algorithms in programming!


Next Steps

Get ready for Day 11: Sum of Numbers, where you’ll create a program that calculates the sum of all numbers from 1 to a user-provided number n.