# Time Complexity: Primality

# Time Complexity: Primality

+ 9 comments Basic Python 3 solution:

from math import sqrt def isPrime(p): if p < 2: return False elif p <= 3: return True elif p % 2 == 0 or p % 3 == 0: return False else: for i in range(3, int(sqrt(p)+1), 2): if p % i == 0: return False return True

- We only need to check up to square root of
*p*. - We iterate over the range in increments of 2 for odd numbers only because even numbers are not prime except for 2.

- We only need to check up to square root of

+ 2 comments Somewhere I have seen this task...

`Day 25 of 30.`

+ 6 comments This algorithm isn't O(sqrt(n)), though; since n should be the size of the input not the number itself. The algorithm is exponential on the size.

+ 5 comments ### Java solution - passes 100% of test cases

O(n^(1/2)) solution. We also skip even numbers for faster results.

Alternatively, we could do preprocessing using the Sieve of Erasthenes and save the primes (up to a certain number) in an array or HashSet. Then determing if a number is prime would take O(1) time since it would be a simple lookup.

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) { return true; } else if (n % 2 == 0) { return false; } int sqrt = (int) Math.sqrt(n); for (int i = 2; i <= sqrt; i ++) { if (n % i == 0) { return false; } } return true; } }

From my HackerRank Java solutions.

+ 1 comment Hi guys! I'm quite new here so feel free to point me somewhere if this is not the right place for this post

I claim that the test cases are not checking for one fringe case, they lets solutions through with an error. (Found it when reviewing my own code for an interview that had this error :P )

The case is when we have a number that is a square of a prime (ex 289 = 17*17), this should be NOT PRIME, but my algorithm says on manual input PRIME and still passes all test-cases given for "submit code"

In code this issue can be caused when we mess up loop boundries like: for i in range(3,sqrt(n)): ...

which in Python does not include the actual number sqrt(n), but stops right before. This is ok for all cases except squares of primes, but it will let erroneous code through.

So I would sugest extending one of the test-cases with checking for a: "squared prime number == NOT PRIME" to catch this in the future

Sort 185 Discussions, By:

Please Login in order to post a comment