PRIME1 possible with Python?

dusty 2005-11-03 18:05:01 UTC #1

Hi,
I am trying to solve PRIME1 with Python but fail as the time limit is always exceeded. I first tried with a brute force method (very slow), then with the sieve of Eratosthenes (still too slow). I achieve the best results with testing the numbers for primality with the Rabin-Miller test - but it's still far too slow.

On my machine (1.2Ghz Athlon) my best implementation lasts for this input (worst case):

1
1000000000 1000100000

around 3 seconds which seems to be too slow for the (slower) machines at SPOJ.

However, I saw that there are various solutions in python, so there has to be some solution, could you give me a hint which of the above algorithms you chose?

Best Regards,
Hermann

UncleTimmy 2005-11-06 00:50:40 UTC #2

A sieve is definitely the way to go on this one.

You should be able to get that, say, 10x faster with a better sieve without undue effort (e.g., my PRIME1 Python program does that range in about 0.05 seconds, including output time, but on a 3.4GHz P5 box).

The problems here are a lot of fun, but the relentless "solitariness" of the setup can get frustrating -- there's little opportunity to share knowledge.

The key to getting a fast sieve in Python is to push "the slow bits" into constructs that work at C speed rather than Python speed. I appear to have the fastest Python PRIME1 solution today that's not using psyco (if the MEM column has "a big number", it's using psyco ). Two tricks:[ol]
[li]Don't write a Python loop to "cross out" sieve entries. Use list slice notation instead. For example, rather than

for i in xrange(0, n, 3):
    a[i] = 0

a[0:n:3] = [0] * ((n-1)//3 + 1)

Then you're doing only one statement "at Python speed" rather than (potentially) millions.
[/li]
[li]The obscure idiom

a = filter(None, a)

is by far the fastest way to remove all 0 elements from sequence a (more generally, it removes all "not true" elements).[/li][/ol]
I used those in my program, both to generate all the primes up to sqrt(1000000000) (a one-time startup cost), and in the sieve-over-a-range function.

It can help or hurt to include

import psyco
psyco.full()

That's sped some of my entries by a factor of 6, but slowed others. PRIME1 doesn't need it, although if you do write long-winded Python loops rather than exploit slices, psyco should speed that kind of thing a lot.

billlang 2006-04-14 08:56:04 UTC #3

Hi UncleTimmy, I am trying many times for PRIME1 problem, but time limited at each time.

I am very intrested in your solution. Can you sent your code to me?

my mailbox is bill_lang@ir.hit.edu.cn

Thanks~!

A Guy is loving Python~!

sparr0 2006-04-14 14:52:51 UTC #4

I don't really program in python, I am mostly working from the operations explained in the python tutorial. My first python submission runs in 2.57s using a sieve.

With UncleTimmy's slice trick (very nifty) it drops to 1.36s, and my own benchmarking says that 73% of that is spent printing out the results. I am not savvy to the available low level printing in Python, so I will be content with a ~.37s algorithm.

yamad 2007-10-17 18:58:02 UTC #5

Ok, I'm having the same trouble getting a PRIME1 solution to run under the time limit. I've used the phrases that UncleTimmy suggests above and a sieve algorithm.

My approach now, and no doubt where the performance bottleneck is occurring, is to take a list of all primes up to sqrt(10^9) and look for the lowest value in the range that is divisible by it, and then use that index to 0 all multiples of the prime.

def sieve_prime(m, n, primes):
    '''
    Use the sieve of Eratosthenes to find primes in a range, between m and n
   `primes` is a list of all primes up to sqrt(10^9) (i.e. primes[0:2] = [2, 3, 5]
    '''
    # set up list, excluding even numbers
    if m <= 2:
        s = range(3, n+1, 2)
    elif m % 2 == 0:
        s = range(m+1, n+1, 2)
    else:
        s = range(m, n, 2)
    nroot = int(n ** 0.5)
len_primes = len(primes)
len_s = len(s)

i = 1   # start after 2, where s[0] = 2
while (i < len_primes and primes[i] <= nroot+1):
    p = primes[i]
    for j, d in enumerate(s):
        if s[j]:
            if d == p:
                s[j+p::p] = [0] * (((len_s-1) - (j+p)) // p + 1)
                break
            elif d % p == 0:
                s[j::p] = [0] * (((len_s-1) - j) // p + 1)
                break
    i += 1


if m <= 2:
    return [2] + filter(None, s)
else:
    return filter(None, s)

I suspect that the solution could be faster if I could figure a way to store the list as boolean bits, using the index as the actual number (i.e. s[4] = 0, s[2] = 1, s[11] = 1). But while I got this working with ranges starting from 2, I couldn't get the indexing right for minimum values over 2.

Any tips/hints? Thanks!

hint_sof 2007-12-12 21:37:32 UTC #6

That's not the worst case:

hint_sof 2007-12-15 22:25:00 UTC #7

I've tried 3 different algorithms already (brute force, sieve of Erastothenes and sieve of Atkin) and I keep getting TLE.

As far as the algorithm itself goes, I think it's fast enough (for the sieves), though the problem is the output. I use a string as buffer (buf += str(whatever) + "\n") and then output the entire string (print buf).

Anybody knows a better way for doing this? I believe that if I speed up the output enough, the code will validate...

Best regards

hint_sof 2007-12-15 22:40:23 UTC #8

I've tried 3 different algorithms already (brute force, sieve of Erastothenes and sieve of Atkin) and I keep getting TLE.

Anybody knows a better way for doing this? I believe that if I speed up the output enough, the code will validate...

Best regards

andmart 2008-01-17 05:02:29 UTC #9

I'm filtering the list of elements generated by input range like that:

lista = filter(lambda x: (x % 2 != 0 and x % 5 != 0 and x % 3 != 0 and x % 7 != 0 ), [x for x in xrange(n1, n2)])

ronaeg 2013-10-20 18:19:31 UTC #10

daft_wullie 2013-10-21 12:08:29 UTC #11

What exactly is your question?

As you might see here, it is still possible to get AC in prime1 with pure python 2.7 (and not using psyco).

Just use a sieve. As it was one of my first problems at SPOJ, my own code was very un-optimized. I used a dict to store the primes and precalculated primes up to 31643 which I put into the source. And sys.output of course. Surely this is not the most efficient solution, but it works ...

landgazr 2014-07-09 01:46:22 UTC #12

Hi all!

This is my first post in this forum and I'm a relative newbie to Python and to SPOJ.

I know this is an older thread but I wanted to give my quick two cents on this problem because I really pulled my hair out on this one (I probably should have done a tutorial problem). However, after cruising the forums, I get the impression that the CPython implementation probably was the cause of some of my grief. But I'll be the first to admit it was probably mostly due to my horrible submissions!

Yes, it is possible. And if you do it, give yourself a pat on the back (just look at the Python 3.2.3 submission statistics for PRIME1).

If memory serves me, I began with (more or less) brute force then moved to SOE (was about to move to something like Rabin-Miller or Fermat). Where I kept running into trouble, over and over, was the widening gap between the current value to check and the next composite number as the prime in question got larger. The Python profiler came in handy

I may be totally wrong here, but I was uneasy with some numbers getting flagged multiple times by SOE although in the end I don't think that was translating into huge slowdowns. I became acutely aware of inefficiencies in my algorithm and I got it to progressively run faster and faster on my box and at SPOJ (it was at least encouraging to see those TLEs going to WAs).

The fastest times are around a quarter of a second.

If anyone has any idea on how one could get those kind of times, I'd love to absorb some knowledge (threading? output options other than print? psyco? different sieve?).

Mine got to AC in 4.51 seconds, although on my box with large data sets I got it down to 0.69 seconds (and it was a Celeron).

So, some tips that may get someone just over the hump if trying to solve the Prime Generator problem (PRIME1) with Python on SPOJ:

-> Immutable, unordered data structures (think frozensets, their properties, and what can be done with them...)
-> Don't just use modulus for equality testing. Use that remainder to find more composites immediately.
-> Instead of using SOE to find primes from 2 up to square root of maximum, try using a list of primes ready-made (you already know the data set bounds).
-> Loops aren't healthy on this problem (I guess that's more of a generalization). Keep to a minimum.
-> sorted() will hurt you. range() will kill you.

Basically, my thinking turned from brute force to "OK, now what do I know about the result set after this step has completed?"

Use it to your advantage.

Of course, there is (most likely) room for much, much improvement on my algorithm given the best solution times, but I feel a certain sense of satisfaction that I didn't quit and solved a classical problem.

This n00b is definitely sticking with the tutorial problems next time around.

Best of luck to all!

landgazr 2014-07-09 21:41:45 UTC #13

Update From My Previous Post

I was able to get the time down to 1.71 seconds!!! Still not in the ballpark of the fastest times, so if anyone has any suggestions I'd still love to hear them (see above post).

So if anyone is looking for help on the PRIME1 problem using Python 3.2.3, list slices apparently work MUCH better than sets and their operations, although the latter will still get you to AC albeit slower.

Again, best of luck to all!

numerix 2014-07-10 08:59:18 UTC #14

1.71 s is a rather good time for PRIME1 with Python 3.2.
A closer look at the ranklist shows that most of the fastest 20 submissions are older submissions using (Python 2.6 and) psyco for acceleration.
You can detect this from the memory usage (37/38 MB). So the really fastest Python 3.2 submission is Francky's 2012 real Python 3.2 solution with an unbelievable runtime of 0.39 s. And I can tell you: That was not the result of two days work. Francky worked on prime sieving for weeks or maybe months and so did I.

When I startet at SPOJ in 2009 PRIME1 was the first problem I worked on. Python 3 was not born, the actual Python version was 2.5. The fastest runtime so far was 0.41 s (using psyco) by fxr and after my first AC submissions to PRIME1 I wondered how that could be possible - my submissions were much slower (I don't remember how slow). But on working on it I found more and more things that could be improved and learned A LOT about (speed) optimizing algorihms in Python.

If you look at the actual ranklist you can conclude that PRIMIE1 is a very good starting point for improving Python skills. But it needs some time.
Reaching Francky's 0.39 s with Python 3.2 will be veeeeery hard, maybe nearly impossible - he is a real prime-genius. But getting below 1 s should be possible after some days of work. So, good luck.

francky 2014-07-10 16:08:09 UTC #15

Thanks for those kind words. numerix is my mentor for prime numbers problems, and my first serious problems.
Try to reach some his top speed was my best motivation when I came here at spoj ; at that time I knew only Python...
A giant, public, thanks to numerix for that boost.
Hope the same will happen with many young psolvers...

landgazr 2014-07-10 17:39:20 UTC #16

I can only hope to solve the number of problems and achieve the high rank that both of you have. Of course, I'm guessing that the road you both took was paved with a lot of mental blood, sweat and tears over many months or even years.

My hats off to you both.

Although being a software developer is my day job, Python has re-ignited in me an elemental love for programming and problem solving. And really, this site is very addicting. It must be that rush of satisfaction upon AC! I'm always on the prowl for a new problem to solve. My undergrad was quite light on algorithms and data structures, so together with SPOJ, I'm reading an algorithms book that is taking me "back to school" as it were. Books provide the theory, SPOJ is providing the practice.

The chapter I'm on right now is focusing on numerical algorithms (SOE, Big O, GCD, etc.) and it's fascinating. Can't wait to get to graphs/networks and trees, but you need to crawl before you walk! I love the challenge, I love to educate myself and have always had an affinity for computers and math. Not preternaturally gifted, but my love of the subjects seems to help me get back up no matter how many times a problem knocks me down. Cementing my new found Python knowledge and maybe, just maybe, becoming more employable are bonuses

I'm having fun again, and I have Python and SPOJ to thank. I'm sharpening the saw and having a blast doing it. I hope to share my hard-fought knowledge in this community but, most of all, learn from all those who have been there. I just think the most important things are to never stop learning, and have fun!

And lastly to you both - nicely, nicely done on your achievements. I can only imagine what you both have learned through the many problems and attempts.

leppyr64 2014-07-11 01:20:12 UTC #17

This desire is why I really enjoy being involved with this forum. Cheers!

kiranta 2014-08-14 07:51:54 UTC #18

aman_sai18 2019-06-27 18:30:23 UTC #19

https://ideone.com/2PEmjl
Whats wrong with my python code,
I used the exact same logic and it got accepted in C++