Error in checking if array members are prime or not

Question

I'm supposed to scan an integer array, and loop through it, printing "Prime" or "Not prime" depending on whether the integer is a prime number or not. It's correct in some cases, while wrong on others (like 33 as an example). Here's my code:

public class Solution {

    public static void main(String[] args) {
        //Declaring the scanner
        Scanner scan = new Scanner(System.in);

        //Getting the number of integers to scan
        int n = scan.nextInt();

        //Declaring a numbers array
        int[] numbers = new int[n];

        //Scanning the integers
        for(int i=0; i<n; i++)
            numbers[i] = scan.nextInt();

        //Determining if numbers are prime
        for(int i=0; i<n; i++)
        {
            boolean isPrime = true;
            for(int j=2; j<n; j++)
            {
                if(numbers[i] % j == 0){
                    isPrime = false;
                    System.out.println("Not prime");
                    break;
                }
            }
            if(isPrime)
                System.out.println("Prime");
        }

    }
}

Answer 1

Here's the updated code

public class Solution {

public static void main(String[] args) {
    //Declaring the scanner
    Scanner scan = new Scanner(System.in);

    //Getting the number of integers to scan
    int n = scan.nextInt();

    //Declaring a numbers array
    int[] numbers = new int[n];

    //Scanning the integers
    for(int i=0; i<n; i++)
        numbers[i] = scan.nextInt();

    //Determining if numbers are prime
    for(int i=0; i<n; i++)
    {
        checkPrime(numbers[i]);
    }

}

private static void checkPrime(int number) {
    boolean isPrime = true;
    int limit = (int) Math.ceil(Math.sqrt(number));
    for(int j=2; j<=limit; j++)
    {
        if(number >2 && number % j == 0){
            isPrime = false;
            break;
        }
    }
    if(number> 1 && isPrime)
        System.out.println(number + " is Prime");
    else
         System.out.println(number + " is not prime");

}

}

Sample output

> 5 
> 1 2 3 4 33

1 is not prime
2 is Prime
3 is Prime
4 is not prime
33 is not prime

Answer 2

Two important points you can consider:

A. You need to check numbers up to its square root i.e. if an integer is not divisible by any integer from 2 to its square root, it is Prime

B. You do not need an additional boolean flag (i.e. isPrime in your code).

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        // Declaring the scanner
        Scanner scan = new Scanner(System.in);

        // Getting the number of integers to scan
        System.out.print("How many numbers: ");
        int n = scan.nextInt();

        // Declaring a numbers array
        int[] numbers = new int[n];

        // Scanning the integers
        for (int i = 0; i < n; i++) {
            System.out.print("Enter number " + (i + 1) + ": ");
            numbers[i] = scan.nextInt();
        }

        // Determining if numbers are prime
        for (int i = 0; i < n; i++) {
            int j, upperRange = (int) Math.sqrt(numbers[i]);
            for (j = 2; j <= upperRange; j++)
                if (numbers[i] % j == 0)
                    break;
            if (numbers[i] != 1 && j > upperRange)
                System.out.println(numbers[i] + " is Prime");
            else
                System.out.println(numbers[i] + " is not Prime");
        }

    }
}

A sample run:

How many numbers: 5
Enter number 1: 256
Enter number 2: 289
Enter number 3: 1
Enter number 4: 5
Enter number 5: 7
256 is not Prime
289 is not Prime
1 is not Prime
5 is Prime
7 is Prime

Answer 3

Consolidating the code and using Math.sqrt() Refactor your code to to this

public boolean isPrime(int number){
 if(number==1){
  return false;
 }
 boolean isPrime = true;
 int maxN = Math.ceil(Math.sqrt(number));
 for(int j=2; j< maxN; j++){
  if(number % j == 0){
    isPrime = false;
    break;
  } 
 }
 return isPrime;
}