# LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

## #1 September 28 2020

transhumanist.liberation
Member

### 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

``````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)`````` ## #2 September 29 2020

VincentKeyboard
Member

### Re: Find the 10 001th prime number

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.

Last edited by VincentKeyboard (September 29 2020) ## #3 September 29 2020

new_user
Member

### Re: Find the 10 001th prime 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. ## #4 September 29 2020

geek
Member ### Re: Find the 10 001th prime number

Have a look at sieves, for example Eratosthenes's: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ## #5 September 30 2020

NuclearVision
Member ### Re: Find the 10 001th prime number

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. ## #6 October 20 2020

Joe
Member ### Re: Find the 10 001th prime number

geek wrote:

Have a look at sieves, for example Eratosthenes's: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

\$(@!#&\$#@(%^(@#%^!@#% HE'S ALIVE!!! 