Objective
Today we're learning about running time! Check out the Tutorial tab for learning materials and an instructional video!
Today we're learning about running time! Check out the Tutorial tab for learning materials and an instructional video!
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 .
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.
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.
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.
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.
is only divisible and itself, so we print on a new line.
Solution :
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 0; tc < T; tc++) {
int n = sc.nextInt();
System.out.println(isPrime(n) ? "Prime" : "Not prime");
}
sc.close();
}
static boolean isPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
