Day 25: Running Time and Complexity HackerRank Solution

Day 25: Running Time and Complexity HackerRank Solution
Source : https://www.hackerrank.com/challenges/30-running-time-and-complexity

Objective
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 .

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 primePrimePrime

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.

Source : https://www.hackerrank.com/challenges/30-running-time-and-complexity

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	public class Solution {
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int T = scan.nextInt();
	while (T-- > 0) {
	int n = scan.nextInt();
	System.out.println(isPrime(n) ? "Prime" : "Not prime");
	}
	scan.close();
	}
	private static boolean isPrime(int n) {
	if (n < 2) {
	return false;
	} else if (n == 2) { // account for even numbers now, so that we can do i+=2 in loop below
	return true;
	} else if (n % 2 == 0) { // account for even numbers now, so that we can do i+=2 in loop below
	return false;
	}
	int sqrt = (int) Math.sqrt(n);
	for (int i = 3; i <= sqrt; i += 2) { // skips even numbers for faster results
	if (n % i == 0) {
	return false;
	}
	}
	return true;
	}
	}