HackerRank içerisinde bulunan “Time Complexity: Primality” sorusunun açıklaması ve çözümü. Bu soruda size verilen bir sayının asal sayı olup olmadığını O(sqrt(n)) zamanında bulmanız isteniyor.

► HackerRank – Time Complexity: Primality: https://www.hackerrank.com/challenges/ctci-big-o/problem

► Problem açıklaması:

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

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

Sample Input

STDIN Function

—– ——–

3 p = 3 (number of values to follow)

12 n = 12 (first number to check)

5 n = 5

7 n = 7

Sample Output

Not prime

Prime

Prime

Explanation

We check the following integers for primality:

n = 12 is divisible by numbers other than 1 and itself (i.e.: 2, 3, 4, 6).

n = 5 is only divisible 1 and itself.

n = 7 is only divisible 1 and itself.