We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
Time Complexity: Primality
You are viewing a single comment's thread. Return to all 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.
From my HackerRank Java solutions.