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.
I was playing around with the Sieve based approach first (using a bit Array) but it timed out, eventually changing back to the brute force approach division up to Sqrt(n) passed all the test cases. (C#)
Hi. I'm surprised it timed out for you. Here's my attempt at coding the Sieve of Eratosthenes functions. I made some optimizations that may be useful for your code. (The code is general and is from a problem from "cracking the coding interview")
Same. I even did a version where I had a boolean array that was half the size of the maximum input to check, given the observation every prime greater than two is odd.
I still ran out of memory.
It's a little frustrating the optimized for time version of this algo runs out of space, forcing you to use the dumb brute force version.
Observe that if a number is composite, it must have a prime factor less than or equal to its square root.
Proof:
0. Let r be a composite number.
1. Assume that prime number q divides r. Let n x n = r, i.e. n is the square root of r. If q < n, we are done.
2. Now suppose that q > n. By assumption r/q is a whole number, and we know that either r/q is prime, or r/q has prime factors of its own.
3. But n = r/n, and r/n > r/q, and r/q > { any prime factors of r/q }, so clearly there exists a prime factor of r smaller than the square root of r, as desired.
This means you only need to create an array of ~46340 booleans (square root of 2 x 10^9) and apply the prime sieve to find the primes in that list. Using that list for your trial divisors will give better time complexity than O(sqrt(n)).
Sieve approaches are to find ALL primes not just check a if a single number is prime. You're solving a more complex problem so you can't be too surprised by a worse run time
Find the largest int in a0, make a sieve up to the square root of that once. Then instead of testing every number less than the square root of each a0, you only are testing the primes less than the squareroot of a0 using the seive you just built. It would cut down on the the number of loops especially for larger numbers.
I had the same experience with sieve and BitArray in C#.
Making the sieve in the first place is just too expensive for this input. If we had many more primes to check, then pre-calculating the sieve and then just quickly referencing it when checking for primality would have been much faster than brute-checking each number individually. But in this case, there are simply too few numbers to check to justify the price of the sieve construction.
But you can pre-calculate prime numbers up to sqrt(n) using seive. Then you can test each number by using just primes, but not all numbers up to sqrt(n), resulting in O(sqrt(n)/log(n)) complexity.
You need to pack each boolean in a single bit (as opposed to the entire byte), which would then fit in ~128 MB. Something like C# BitArray or C++ bitset or specialized vector.
You could use a cache and would only need to go up to sqrt(n), and only need to cache primes since all composites divide into primes. This means you have to walk through sqrt(n) numbers and cache them as you go the first time around. You can do incremental caching as needed but for the full range of the input sqrt(2x10^9) it only ends up being 4674 x 2 bytes each so you're looking at ~ 9kb.
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.
I was playing around with the Sieve based approach first (using a bit Array) but it timed out, eventually changing back to the brute force approach division up to Sqrt(n) passed all the test cases. (C#)
Hi. I'm surprised it timed out for you. Here's my attempt at coding the Sieve of Eratosthenes functions. I made some optimizations that may be useful for your code. (The code is general and is from a problem from "cracking the coding interview")
HackerRank solutions.
Using the Sieve I get an out of memory exception when trying to load one of the test cases:
Same. I even did a version where I had a boolean array that was half the size of the maximum input to check, given the observation every prime greater than two is odd.
I still ran out of memory.
It's a little frustrating the optimized for time version of this algo runs out of space, forcing you to use the dumb brute force version.
Observe that if a number is composite, it must have a prime factor less than or equal to its square root.
Proof:
0. Let r be a composite number.
1. Assume that prime number q divides r. Let n x n = r, i.e. n is the square root of r. If q < n, we are done.
2. Now suppose that q > n. By assumption r/q is a whole number, and we know that either r/q is prime, or r/q has prime factors of its own.
3. But n = r/n, and r/n > r/q, and r/q > { any prime factors of r/q }, so clearly there exists a prime factor of r smaller than the square root of r, as desired.
This means you only need to create an array of ~46340 booleans (square root of 2 x 10^9) and apply the prime sieve to find the primes in that list. Using that list for your trial divisors will give better time complexity than O(sqrt(n)).
Sieve approaches are to find ALL primes not just check a if a single number is prime. You're solving a more complex problem so you can't be too surprised by a worse run time
Find the largest int in a0, make a sieve up to the square root of that once. Then instead of testing every number less than the square root of each a0, you only are testing the primes less than the squareroot of a0 using the seive you just built. It would cut down on the the number of loops especially for larger numbers.
I had the same experience with sieve and BitArray in C#.
Making the sieve in the first place is just too expensive for this input. If we had many more primes to check, then pre-calculating the sieve and then just quickly referencing it when checking for primality would have been much faster than brute-checking each number individually. But in this case, there are simply too few numbers to check to justify the price of the sieve construction.
But you can pre-calculate prime numbers up to sqrt(n) using seive. Then you can test each number by using just primes, but not all numbers up to sqrt(n), resulting in O(sqrt(n)/log(n)) complexity.
Sieve in this problem would require 1 GB of memory for the boolean array to hold all odd integers up to 10^9....
You need to pack each boolean in a single bit (as opposed to the entire byte), which would then fit in ~128 MB. Something like C# BitArray or C++ bitset or specialized vector.
You could use a cache and would only need to go up to sqrt(n), and only need to cache primes since all composites divide into primes. This means you have to walk through sqrt(n) numbers and cache them as you go the first time around. You can do incremental caching as needed but for the full range of the input sqrt(2x10^9) it only ends up being 4674 x 2 bytes each so you're looking at ~ 9kb.
You can save some time by not dividing by even numbers i.e. like in my solution, start i from 3 and increment by 2.
Good point. Same Big-O runtime, but faster results. I updated my solution. Thx.
How does this become O(n^1/2)?
the for loop goes from i = 2 to i = n^(1/2), which is the slowest part of the code, so it's O(n^(1/2))
HackerRank solutions.
nice 1
Thanks very much! I've done it in PHP, I was missing checking for 0 1 and 2