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

Offline

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

Offline

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

Offline

#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

Offline

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

Offline

#6 October 20 2020

Joe
Member

Re: Find the 10 001th prime number

We have already covered this exercise!

geek wrote:

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

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

Offline

Board footer