• Coding

  • Find the 10 001th prime number

Code seems correct because it works for small numbers, but it's unable to process large numbers where did I go wrong
I can find the 6th prime number if the range is small like 2 to 100
Thank you in Advance
prime_numbers = []
for number in (range(2,2000000000)):
    if number > 1:
        for i in range(2, number):
            if number % i == 0:
                break
        else:
            list.append(number)
print(prime_numbers[10001])
you could cache the results of 
    for i in range(2, number):
            if number % i == 0:
                break
        else:
in a hashmap with key being number.

If I understand your code correctly, the inner loop computes "number % i" for 2 till number
for each number from 0 to 2,2000000000-1.
So if you save the results of the inner loop, you only need to compute "number % i" starting from last saved number till current number.
You need to improve the efficiency in order to handle large numbers.
Basic steps that can be done are the following:
- for number in (range(2,2000000000))
here you don't need to loop over all the numbers, you can skip even numbers and numbers ending in 5. Just watch out for the 2 exceptions which are 2 and 5.
- im not sure what the purpose of this line is: if number > 1
- in this line: for i in range(2, number):
you can replace number by number/2. Since we know that the number is odd (step 1) we are sure that it is not divisible by 2 so this number has no factors in the range [number/2:number]
- also regarding this section:
for i in range(2, number/2):
if number % i == 0:
break
You dont really need to do a for loop on all the digits between 2 and number/2. You just need to loop over the prime numbers between 2 and number/2 which you can easily collect in a list in previous iterations.

These are basic improvements that would slightly enhance the performance of your code but do not guarantee finding large prime numbers. You can look for more advanced algorithms online.
I remember solving this as a child, check the tips all the members suggested, they're really useful.
But what helped most was the following:
You don't need to check if the number was dividable but all numbers from 2 to number, you can check if it's dividable by any number from 2 to the square root of this number, if there are none it means that this is a prime number. This will spare a lot of memory.
A few more optmizations and the code should work.
20 days later