-1

My Jupyter Notebook gets stuck in run mode whenever i run the shell with the following code:

def is_prime(num):
    if num < 2:
        return False  
    for x in range(2, num - 1):
        if num % x == 0:
            return False  
    return True  

prime_list = []    
num = 2

while True:    
    if is_prime(num):
        prime_list.append(num)
    num += 1
if len(prime_list) == 10002:
    break


print(prime_list[-1])

Could someone please run this code on their computer and tell me what the output is? I'd really appreciate any answer.

chevybow
  • 9,959
  • 6
  • 24
  • 39
STACKER
  • 1
  • 1

1 Answers1

0

Your code is getting stuck because your prime testing function becomes very slow!

I ran your code with varying stopping points of 100, 1000, 2000, and 4000 prime numbers found. The runs took 0.01, 0.23, 0.98, and 4.31 seconds, respectively.

You can see that doubling the number of primes to find (roughly) quadruples the amount of time taken. This makes sense, given that to test if n is prime, you have to check it against n-2 other numbers (you exclude 1 and n). So, your algorithm has a time complexity of at least O(n^2) to find n prime numbers.

(also, I got 104759 after 10002 prime numbers were found in 30 seconds. I accidentally typed "100002" at first, which sat running for quite a long time without any results...)

chemicalcrux
  • 185
  • 10
  • chemicalcrux thank you so much for your answer it was really helpful – STACKER Jun 29 '18 at 15:28
  • If you want to learn more about how to find prime numbers in reasonable time, check out the [Sieve of Eratosthenes](https://stackoverflow.com/questions/3939660/sieve-of-eratosthenes-finding-primes-python) - it's a pretty straightforward algorithm, and I can find the largest prime less than 1,000,000 in *0.21 seconds* with it! – chemicalcrux Jun 29 '18 at 15:31