A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**transhumanist.liberation****Member**

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

**VincentKeyboard****Member**

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

**new_user****Member**

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.

**geek****Member**

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

**NuclearVision****Member**

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.

**Joe****Member**

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

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

Pages: **1**