Day 25: Running Time and Complexity

Task 
A prime is a natural number greater than  that has no positive divisors other than  and itself. Given a number, , determine and print whether it's  or .

Note: If possible, try to come up with a  primality algorithm, or see what sort of optimizations you come up with for an  algorithm. Be sure to check out the Editorial after submitting your code!

Input Format

The first line contains an integer, , the number of test cases. 
Each of the  subsequent lines contains an integer, , to be tested for primality.

Constraints

Output Format

For each test case, print whether  is  or  on a new line.

Sample Input

3
12
5
7

Sample Output

Not prime
Prime
Prime

Explanation

Test Case 0: . 
 is divisible by numbers other than  and itself (i.e.: , , ), so we print  on a new line.

Test Case 1: . 
 is only divisible  and itself, so we print  on a new line.

Test Case 2: . 
 is only divisible  and itself, so we print  on a new line.

풀이

package Day25;

import java.util.Scanner;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. */
        Scanner sc = new Scanner(System.in);
        int size = sc.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            int num = sc.nextInt();
            if (checkPrime(num)) sb.append("Prime").append(System.lineSeparator());
            else sb.append("Not prime").append(System.lineSeparator());
        }
        System.out.println(sb.toString());
    }

    private static boolean checkPrime(int num) {
        if (num == 1) return false;
        if (num == 2) return true;
        if (num / 2 > 2) num = num / 2;
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}