LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 4 weeks ago

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
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])``````

#2 4 weeks ago

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 (4 weeks ago)

#3 4 weeks ago

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 4 weeks ago

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 4 weeks ago

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 5 days ago

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

\$(@!#&\$#@(%^(@#%^[email protected]#% HE'S ALIVE!!!