Find sum of first 1000 prime numbers in python

Question

I have written a program which counts the sum of the primes uptill 1000. The program is as follows:

limit = 1000

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

sum = 0
for i in range(2, int(limit+1)):
    if is_prime(i):
        sum = sum + i
        count += 1
print sum

What changes can I make to find 1000 primes instead of upto 1000 numbers? Also, I am looking for space complexity as O(1) and time complexity as O(n) (As I know other methods can do it :-) such as "Sieve of Eratosthenes" and finding prime while iterating upto sqrt(n) http://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/)

Please correct me if I am going wrong some where. Thank you.

Not sure how you get O(n) time, especially when limited to O(1) space. — Mark Ransom, Apr 14 '15 at 01:32
@Anonymous, This question has lots to do with that, but it provides lots of info to the OP, but there's some differences... — Zizouz212, Apr 14 '15 at 01:33
The sieve of eratosthenes finds primes in constant space and, what, like n log n time, but it is fundamentally limited to a maximum. — jwilner, Apr 14 '15 at 01:47
@jwilner: The sieve of Eratosthenes is neither constant space nor n log n time. I'm not sure what you mean by "fundamentally linked to a maximum" but you can extend the list incrementally, it is just not as efficient. However, you can simply estimate the 1000th prime and sieve out a slightly larger interval. — Douglas Zare, Apr 14 '15 at 02:07
@DouglasZare: I think by "fundamentally linked to a maximum" jwilner is referring to the fact that we can decide in the beginning the range of numbers that we want to support (say, up to 10mil). But I agree that "constant space" and "n log n time" is a common misconception, I also often do that. I (and I believe jwilner) feel that it's constant space because once we pick certain upperlimit (say <= 10mil), we can process all primes under 10mil in constant space and n log n time. However, the correct understanding should see that it's the scaling with larger limit which determines the complexity — justhalf, Apr 14 '15 at 02:23
@justhalf: As I stated, you can extend the list incrementally, but this is less efficient than the usual sieve of Eratosthenes. See the Wikipedia page. The space needed increases with n. If you call that constant space, what wouldn't be constant space? The prime number theorem says that the nth prime is roughly n log n, so to find the first n primes you need to sieve out about n log n numbers, and with a naive sieve, that means you use n log n space. Then you use about n log n loglog n time, since sieving up to x=n log n takes about x log log x time. I'm not sure where you get n log n. — Douglas Zare, Apr 14 '15 at 02:34
First, I already acknowledged that to say it uses constant space is incorrect. Next, I think I consider "n" in the "n log n time" to be the upper limit, instead of the nth prime. — justhalf, Apr 14 '15 at 02:36
@justhalf: Reread what I said. You gave me no information that I did not already say. By the way, to sieve up to n, for each prime p, you do about n/p operations, for n loglog n total, not n log n. — Douglas Zare, Apr 14 '15 at 02:47
@DouglasZare: Yes, precisely, I said "I already acknowledged" because your comment didn't give new information to me neither! =). And yeah, I think you're correct about it being n log log n. — justhalf, Apr 14 '15 at 02:48
Just realized I said constant space and not linear -- whoops. My guess at the time complexity was just that, a guess, but is clearly wrong. Anyway, I'm done spreading misinformation for the night. — jwilner, Apr 14 '15 at 02:53
@Deep: You say other methods can do this in constant space and O(n) time. Those are surprising to me. Do you have a link to those methods? Your own algorithm for getting primes up to n is something like O(n^2/log n) because your is_prime method is terribly inefficient, since you use trial division up to p-1 to recognize a prime p though you could stop at sqrt(p). So, your own code is really inefficient, but you say you want an extremely efficient answer. — Douglas Zare, Apr 14 '15 at 13:28
@DouglasZare - I was talking about other methods as in "Sieve of Eratosthenes" and finding via iterating upto sqrt(n). I have updated the question. Also, I updated the function to learn in a diff way. :-) — deep, Apr 14 '15 at 18:27
The sieve of Eratosthenes is not O(n). I already pointed out that using the sieve of Eratosthenes to find the first n primes takes O(n log n loglog n) steps. Again, I would be surprised to see an O(n) algorithm, and maybe you shouldn't be so certain there is one, while your own code is close to O(n^2). — Douglas Zare, Apr 14 '15 at 18:53

Saksham Varma · Answer 1 · 2015-04-14T02:22:23.740

1

Code:

def f():
    i = 2
    while True:
        if all(i % x != 0 for x in range(2, i-1)):
            yield i
        i += 1

primes = f()
print sum(primes.next() for _ in range(1000))

Or a one liner:

import itertools
print sum(itertools.islice(itertools.ifilter(lambda x: all(x % i != 0 for i in range(2, x)), f()), 0, 1000))

edited Apr 14 '15 at 02:22

answered Apr 14 '15 at 01:42

Saksham Varma

2,122
13
15

zhangwt · Accepted Answer · 2015-04-14T05:48:54.947

1

Just a small improvement based on your code to find limit primes instead of limit numbers.

limit = 1000

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

sum = 0
num = 2
for i in xrange(limit):
    while not is_prime(num):
        num += 1
    sum += num
    num += 1 # sorry, miss this
print sum

And you could also use a single loop when looking for certain amount of things you are interested in, it could be just a matter of taste.

limit = 1000

def is_prime(n):
    for i in range(2, n):
        if n%i == 0:
            return False
    return True

sum = 0
count = 0
num = 2
while count != limit:
    if is_prime(num):
        sum += num
        count += 1
    num += 1

print sum

edited Apr 14 '15 at 05:48

answered Apr 14 '15 at 02:17

zhangwt

350
1
2
12

The answer should b 3682913. I am getting 2000 with the above code..Any inputs? Thanks – deep Apr 14 '15 at 05:37
Sorry, forget to increase `num` by 1 when it is a prime :( – zhangwt Apr 14 '15 at 05:42
1

Just one more thing, `sum` is a built-in function of python, using it as variable name would override it. Just be aware of that. – zhangwt Apr 14 '15 at 06:01

Jose Ricardo Bustos M. · Answer 3 · 2015-04-14T08:08:29.040

0

I wish to propose the following algorithm (Sieve of Eratosthenes)

n=1000
limit_sieve = 10000
primes = set()
notPrimes = set()
i = 2
while len(primes)<n:
  if not i in notPrimes:
    primes.add(i);
    for notPrime in range(i*2, limit_sieve, i):
      notPrimes.add(notPrime)
  i+=1

sum(primes)

edited Apr 14 '15 at 08:08

answered Apr 14 '15 at 08:01

Jose Ricardo Bustos M.

8,016
6
40
62

1

No problem, the limit of the sieve is related to n, through the cumulative distribution of the prime numbers, if n changes then the limit too – Jose Ricardo Bustos M. Feb 10 '21 at 17:34
The sieve limit would be huge for so great values of n, it would make the algorithm very very very inefficient – Jose Ricardo Bustos M. Feb 10 '21 at 18:32

jwilner · Answer 4 · 2015-04-14T01:49:01.620

The simplest way to do what you've requested is probably with itertools.

def gen_primes():
    for i in itertools.count(2):
        if is_prime(i):
            yield i 

first_one_thousand = list(itertools.islice(gen_primes(), 1000))

Shoot, everyone likes a one-liner:

first_one_thousand = list(itertools.islice((i for i in itertools.count(2) 
                                            if is_prime(i)), 
                                           1000))

Find sum of first 1000 prime numbers in python

4 Answers4

Linked