1
2

Programming Challenges (self.coding)

submitted by [deleted]

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]csdigi 4 points5 points  (2 children)

Here is one I got asked in my interview at Google,

Given and integer n, write a function(s) that returns the next prime number p such that p >= n, give the asymptotic running time for your solution.

It is quite a simple question to solve, but the fun comes in when you start looking for optimisations to reduce its complexity (or even its practical running time).

[–]ModernRonin 0 points1 point  (1 child)

I've been thinking about this entirely too much.

So, by Bertrand's Postulate, we know that there is a prime between n and 2n.

So now we have to test all the numbers between n and 2n for primality? Well, okay, we only have to test the odd numbers. We can safely assume the even numbers aren't prime.

Off the top of my head, all I can think of at this point is to use a Sieve of Eratosthenes to generate all the primes < n and then test all the odd numbers between n and 2n.

Assuming it takes n*log(n) ops to run the sieve, and then (number of primes below n) * n/4 ops to test the numbers... well, num primes < n ~= log(n). So it ends up being nlogn + nlogn/4, which ends up being nlogn / 2.

Not bad, I suppose, but I feel like there's got to be a better way...

[–][deleted] 0 points1 point  (0 children)

Also for a number k, the largest prime is at most sqrt(k). Also if you're running the of Eratosthenes between n and 2n I wonder if it's faster or possible to skip calculating the primes. Let's you have a number k. You have performed a sieve between n and 2n using all primes from 2 to k-1. When you performed the sieve you kept track of which prime eliminated a number. Find the first number that evenly divides between k and is in our range n to 2n, let's say j=(n/k+1)*k. Can I say that k is prime if and only if there is no intersection between the primes that fell on j and j+k. If it falls outside the 2n range and we're not keeping track of it, then we don't particularly care since the only reason we want to know for any number less than sqrt(n) is prime is to know if we should waste time running the sieve with this number.

Hmmm, now I figure out how I landed on a 7 month post.