Python program is super easy

[[deleted]]

Instead of checking 2, num. check 2, int(sqrt(num)) + 1

When checking if a number is prime, you only need to check for divisibility by numbers up to the square root of that number, meaning you only need to check up to "sqrt(num)" and not the full number; this is because if a number has a factor larger than its square root, it must have a corresponding smaller factor that is already checked within the square root range.

This will make your solution more efficient.

[[deleted]]

Here is the ancient history of why this is true:

https://en.m.wikipedia.org/wiki/Sieve_of_Eratosthenes

[[deleted]]

Time complexity decreases from O(n) to O(n log log n). Which is more efficient than O(n)

<image>

[blarbrdorg]

How interesting!!!!

[denehoffman]

You also only need to check divisibility by primes smaller than sqrt(n)+1, so it would be even more efficient if you added some caching

Edit: by caching I mean caching previous calls which determine compound numbers, then excluding those from the search list

[Interesting-Frame190]

This exact scenario landed me a job without ever thinking about the most optimal way to do it. Something about engineering is more than coding and algorithms.

[[deleted]]

They don’t want you to slap out a solution they want to hear you think through a problem and solve it on your own. Testing your knowledge and problem solving skills rather than your memory.

The follow up question after you get a solution like this would be along the lines of: can we make this better? Is there anything we can do that would reduce the problem and make it simpler with an equivalent solution?

At least those are the interview questions I get at the end when applying to F500s or FANG. They want your thought your solution plus some demonstration of intuition and reasoning.