Time Complexity: Primality HackerRank Solution

Time Complexity: Primality HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-big-o

A prime is a natural number greater than that has no positive divisors other than and itself. Given integers, determine the primality of each integer and print whether it is Prime or Not prime on a new line.

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

Function Description

Complete the primality function in the editor below. It should return Prime if is prime, or Not prime.

primality has the following parameter(s):

• n: an integer to test for primality

Input Format

The first line contains an integer, , denoting the number of integers to check for primality.
Each of the subsequent lines contains an integer, , the number you must test for primality.

Constraints

Output Format

For each integer, print whether is Prime or Not prime on a new line.

Sample Input

31257

Sample Output

Not primePrimePrime

Explanation

We check the following integers for primality:

1. is divisible by numbers other than and itself (i.e.: , , , ), so we print Not prime on a new line.
2. is only divisible and itself, so we print Prime on a new line.
3. is only divisible and itself, so we print Prime on a new line.

Source : https://www.hackerrank.com/challenges/ctci-big-o

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	// Time Complexity: O(n^(1/2)) for each
	// Space Complexity: O(1)
	public class Solution {
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int p = scan.nextInt();
	while (p-- > 0) {
	int n = scan.nextInt();
	System.out.println(isPrime(n) ? "Prime" : "Not prime");
	}
	scan.close();
	}
	public 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;
	}
	}