0

I am trying to list down all the prime numbers up till a specific number e.g. 1000. The code gets slower as the number increase. I am pretty sure it is because of the for loop where (number -1) is checked by all the prime_factors. Need some advise how I can decrease the processing time of the code for larger numbers. Thanks

import time

t0 = time.time()
prime_list = [2]
number = 0
is_not_prime = 0
count = 0
while number < 1000:
    print(number)
    for i in range (2,number):
        count = 0
        if (number%i) == 0:
            is_not_prime = 1
        if is_not_prime == 1:
            for j in range (0,len(prime_list)):
                if(number-1)%prime_list[j] != 0:
                    count += 1
            if count == len(prime_list):
                prime_list.append(number-1)
                is_not_prime = 0
                count = 0
                break
        
    number += 1
print(prime_list)
t1 = time.time()

total = t1-t0
print(total)
Ajin
  • 1

1 Answers1

0

Your solution, on top of being confusing, is very inefficient - O(n^3). Please, use the Sieve of Eratosthenes. Also, learn how to use booleans.

Something like this (not optimal, just a mock-up). Essentially, you start with a list of all numbers, 1-1000. Then, you remove ones that are the multiple of something.

amount = 1000

numbers = range(1, amount)
i = 1
while i < len(numbers):
  n = i + 1
  while n < len(numbers):
    if numbers[n] % numbers[i] == 0:
      numbers.pop(n)
    else:
      n += 1
  i += 1

print(numbers)

Finally, I was able to answer because your question isn't language-specific, but please tag the question with the language you're using in the example.

Sean AH
  • 486
  • 4
  • 8
  • Ya that was my first try.. third day of coding. btw its python. Anyhow, I tried to understand Sieve of Eratosthenes and wrote this code thats very similar to the logic you just explained: `t_in = time.time() number_list = [] number = 1 while number<100000: number += 1 number_list.append(number) i = 2 while i < number: for j in number_list: if(j%i)==0: if(j!=i): number_list.remove(j) i += 1 t_out = time.time() total = t_out-t_in print(total, number_list)` – Ajin Oct 31 '21 at 20:06
  • So what do you need help with now? – Sean AH Oct 31 '21 at 20:08
  • nothing. Thanks :) – Ajin Oct 31 '21 at 20:20
  • Ok. You can mark it as accepted if it answers the question. – Sean AH Oct 31 '21 at 20:22