Prime Generator(for Spoj solution)

Question

I have several days struggling with this Prime Generator algorithm for SPOJ problem. The problem state to print at least 100000 primes from a number m,n with n<=1000000000 in 6 seconds. I have this implementation that print 100000 prime in 11.701067686080933 seconds. is it possible to beat the time restriction(6s) in Python. I feel that I miss something in my segmented sieve function , cause I just implemented it how I understand the algorithm work, maybe a change can make it better.

Some Help would appreciated here.

def sieveOfErosthen(m):
    limit=m+1
    prime=[True]*limit

    for i in range(2,int(m**0.5)):
        if prime[i]:
            for x in range(i*i,limit,i):
                prime[x]=False
    return prime  

def segmentedSieve(m,n):
    limit= n+1
    segment=[True]*limit

    for j in range(2,int(n**0.5) ):
        if sieveOfErosthen(j):
            for b in range(j*(m//j),limit,j):
                if b >j:
                    segment[b]=False
    for v in range(m,limit):
        if segment[v]:
            print(v)
    return True

Answer 1

This code is a disaster. Let's begin with the most glaring error:

if sieveOfErosthen(j):

(This is particularly confusing as your original code didn't define this function but instead defined EratosthenesSieve() -- later editors of your post mapped one onto the other which I'm assuming is correct.) What does sieveOfErosthen(j) return? It returns an array, so in the boolean context of if, this test is always True, as the array always contains at least one element if j is positive!

Change this to if True: and see that your output doesn't change. What's left is a very inefficient sieve algorithm, which we can speed up in various ways:

def segmentedSieve(m, n):
    primes = []
    limit = n + 1
    segment = [True] * limit

    if limit > 0:
        segment[0] = False

        if limit > 1:
            segment[1] = False

    for j in range(2, int(limit**0.5) + 1):
        if segment[j]:
            for b in range(j * j, limit, j):
                segment[b] = False

    for v in range(m, limit):
        if segment[v]:
            primes.append(v)

    return primes

This code can easily find the first 100,000 primes in a fraction of a second, But ultimately, if n <= 1000000000 (a billion) then we have to assume the worst case, i.e. the last 100,000 primes in 6 seconds for some suitable m in segmentedSieve(m, 1000000000) which will take this code minutes not seconds.

Finally, you didn't implement a segmented sieve -- you implemented a regular sieve and just skimmed off the requested range. I recommend you read about segmented sieves in Wikipedia, or elsewhere, and start over if you need a segmented sieve.

Answer 2

For solving this problem you have to use Segmented sieve. there are some good resources please check these geeksforgeeks quora

https://discuss.codechef.com/questions/54416/segmented-sieve https://github.com/calmhandtitan/algorepo/blob/master/numberTheory/sieve_fast.cpp