Identify Prime Numbers

Identify Prime Numbers

Question

Write an algorithm to identify prime numbers from a list of numbers ranging 0-100.

Solution

The main question is actually to write a program to check if a number is prime. There are 4 situations.

  1. If number is 0 or 1, it is not prime.

  2. if the number is 2, it is prime.

  3. if the number is even, it is not prime.

  4. if number is greater than 3, and not divisible by all odd numbers (except 1) smaller than the square root of the input number, it is prime.

Sample

public class InterviewPracticeExtra05 {

    private static boolean is_prime(int input) {
        if (input <= 1) return false;
        if (input == 2) return true;
        if (input % 2 == 0) return false;
        for (int i = 3; i * i <= input; i += 2) {
            if (input % i == 0) return false;
        }
        return true;
    }
    
    public static void main(String[] args) {
        for (int i = 0; i <= 100; i++) {
            if (is_prime(i)) System.out.println(i);
        }
    }
}

Reference