Hackerrank - Time Complexity: Primality Solution
1 min read

Hackerrank - Time Complexity: Primality Solution

Hackerrank - Time Complexity: Primality Solution

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

3
12
5
7

Sample Output

Not prime
Prime
Prime

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.

Solution in Python

from math import sqrt

def primality(n):
    if not n%2 and n!=2 or n==1: return "Not prime"
    for i in range(3,int(sqrt(n))+1,2):
        if not n%i: return "Not prime"
    return "Prime"

for _ in range(int(input())):
    n = int(input())
    print(primality(n))

Enjoying these posts? Subscribe for more


Adblocker detected! Please consider reading this notice.

We've detected that you are using AdBlock Plus or some other adblocking software which is preventing the page from fully loading.

That's okay. But without advertising-income, we can't keep making this site awesome.

We don't have any banner, Flash, animation, obnoxious sound, or popup ad. We do not implement these annoying types of ads!

We need money to operate the site, and almost all of it comes from our online advertising.

Please add thepoorcoder.com to your ad blocking whitelist or disable your adblocking software.

×