Question

Hey all! So I m almost done with a problem that I started working on for school that deals with the Sieve of Eratosthenes. I managed to get the program to print out all the prime numbers from 2 to the square root of 1000. However, my teacher is asking me to use the Prime Number Hypothesis (?) by C.F. Gauss. This is what he says: C. F. Gauss hypothesized that (N) the number of primes less than or equal to N is defined as (N) = N/loge(N) as N approaches infinity. This was called the prime number hypothesis. In a for loop print the prime numbers, a counter indicating its ordinal number (1, 2, 3, etc.) and the value of (N).

I tried making another for loop, and printing the prime numbers but it s just not working for me! :( ugh. Any help would be greatly appreciated! :)

import math
def sieves(N): 
    x = 1000*[0]        
      prime = 2
      print( 2 )
      i = 3
      while (i <= N):
         if i not in x:
            print(i)
            prime += 1
            j = i
            while (j <= (N / i)):
               x.append(i * j)
               j += 1
         i += 2
      print("
")
def main():
    count = 0
    for i in range (1000):
       count = count + 1
    print(sieves(math.sqrt(1000)))

main()

Answer 1

The problem seems to be in the line j=i. You want to start j = 1 so that you catch all multiples of i and add them to your "x" list of non-prime elements. If you start j = i you will miss some. And when you test for "i not in x" it will evaluate to true for some non-primes.

Also instead of x.append(i*j) you probably meant x[i*j] = 1 (i.e. set to 1 means i*j == not prime) With that modification "i not in x" can be optimized to "x[i] == 0", no reason to search the entire array. This would be a lot more efficient than keeping a sparse array "x" and having to search it s elements every step in the loop.

友情链接