Java Day 25: Running Time and Complexity



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



  1. import java.util.Scanner;
  2. public class Solution {
  3. public static boolean isPrime(int n) {
  4. for (int i = 2; i <= Math.sqrt(n); i++) {
  5. if (n % i == 0) {
  6. return false;
  7. }
  8. }
  9. return true;
  10. }
  11. public static void main(String[] args) {
  12. Scanner in = new Scanner(System.in);
  13. int T = in.nextInt();
  14. for (int i = 0; i < T; i++) {
  15. int n = in.nextInt();
  16. if (n >= 2 && isPrime(n))
  17. System.out.println("Prime");
  18. else System.out.println("Not prime");
  19. }
  20. in.close();
  21. }
  22. }