Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
SPOJ: Prime Generator
Author Message
riveryu

Posted: Fri Sep 04, 2009 11:09 am   Post subject: SPOJ: Prime Generator

Hi guys, I just signed up for SPOJ and I started doing the problems. The second one I'm doing is Prime Generator (PRIME1).

At first I tried a probabilistic primality test using Fermat's Lesser Theorem and a theorem related to quadratic probing. It timed out on my own laptop. Then I tried Miller-Rabin, it was slow and gave me wrong answers sometimes. I'm working on an optimized segmented sieve of Eratosthenes right now, it should work for that problem but I want to learn more. I'm having some trouble finding good material on this kind of stuff. Even google fails me.

Does anyone know any sites that has plain English description about prime test/sieve algorithms? (I'm too poor/cheap/lazy to get books)

Yes, I know about Wikipedia, its too short and technical (I have to DFS the links to words I don't know on each page and it gets annoying).

Shah-Cuber

Posted: Fri Sep 04, 2009 11:28 am   Post subject: Re: SPOJ: Prime Generator

PRIME1 is kinda tricky at the beginning, but the solution I had was simple:
Use sieve for all values, and check if each value is a prime or not (boolean)
Then just divide the input into two parts, before 10^6 and after 10^6, and you could have a separate algorithm for input of 999900000 - 1000000000 (worst case scenario)
also, Miller-Rabin is too slow for this, try using C/C++, i began with Java/python ... but it was too slow, certainly not O(log n) ...
I also recommend this article(below) for a fast implementation of sieve of Eratosthenes(segmented), which for any prime numbers in the subinterval [P,Q], which according to them can result in A (Q-P) log(log(Q))+B pi(sqrt(Q)) time, but if you just don't want to learn that, just search it on wolfram mathworld
Hope that helps ...

Analysis Mode

Posted: Fri Sep 04, 2009 3:49 pm   Post subject: RE:SPOJ: Prime Generator

I didn't look at that link, but you don't need any h4x sieve implementations.

Here's a hint: You don't sieve the entire 1..1000000000. Sieve part of it and use the information obtained in a cleverer way.
saltpro15

Posted: Fri Sep 04, 2009 9:41 pm   Post subject: RE:SPOJ: Prime Generator

you are attempting to use a laser guided nuclear bomb to squash a fly There is a much simpler way to do this as Shah-Cuber and Analysis Mode have already hinted
A.J

Posted: Fri Sep 04, 2009 9:46 pm   Post subject: RE:SPOJ: Prime Generator

I believe the saying is 'using a sledge hammer to kill a fly', but it conveys the same message.

I too believe that overlooking the obvious is an all too common mistake in this question.
riveryu

Posted: Fri Sep 04, 2009 10:33 pm   Post subject: Re: SPOJ: Prime Generator

Well I could be killing a fly right now, but I want to to know more about my sledge hammer since the best solution ran at 0.00 sec and I want to beat it now. If only I can see how long his code was.

@Shah-Cuber
Thanks, but I already thought of the workable solution.
Basically, sieve up to sqrt(n) + 1 first, and then sieve m <-> n.

@Analysis Mode
I looked at that site and his source code (which was > 400 lines) but can't understand his "improvements".
However, I did try to do some pre-sieving, tying to make my algorithm completely ignore numbers divisible 2,3,5 described on another site. This makes the numbers to be considered to be decreased by a factor of ~3.75.
riveryu

Posted: Sat Sep 05, 2009 1:51 pm   Post subject: Re: SPOJ: Prime Generator

I made my short version of sieve of erasto. SPOJ gave me "wrong answer" and I can't figure out why. Someone help?
I'm new to C++, and I had to a lot of review to write this question in C++.
Don't tell me its one of output format mistakes...

prime4.cpp
Description:
 why....

Filename:  prime4.cpp
Filesize:  1.79 KB

saltpro15

Posted: Sat Sep 05, 2009 2:37 pm   Post subject: RE:SPOJ: Prime Generator

SPOJ has a forum too, but I'll take a look

Shah-Cuber

Posted: Sat Sep 05, 2009 3:03 pm   Post subject: Re: SPOJ: Prime Generator

It only took me a minute till I found a wrong answer: if you put in the input; 1 2 10, your program outputs 3 5 7, when it's suppose to be 2 3 5 7 (inclusive), I think you can figure out your problem yourself =P
Also, i don't think your sieve is efficient enough for this ...

Edit: On an unrelated note, are you the same River from A.Y.J?
riveryu

Posted: Sat Sep 05, 2009 4:31 pm   Post subject: RE:SPOJ: Prime Generator

@Shah-Cuber
Ok I fixed that and it was stupid mistake of reusing variables. And yea I am. Also, this code ran 999900000-1000000000 instantly on laptop at least.

I fixed the mistake and submitted again, wrong answer again...
Cyril

Posted: Tue Sep 08, 2009 9:28 pm   Post subject: RE:SPOJ: Prime Generator

I think deterministic Miller-Rabin is quite feasible for this. Just use witnesses 2, 7, and 61. Considering that Python has a built-in pow(a,b,m), which computes a^b mod m with binary exponentiation... you can afford to be quite lazy.

Of course, being noble, I implemented the double sieve method first. (my first lazy Miller-Rabin attempt got WA, so I gave up.)
A.J

Posted: Tue Sep 08, 2009 9:43 pm   Post subject: RE:SPOJ: Prime Generator

Nice to have you back, Cyril. And I believe that Miller-Rabin is actually useful, and is good practice. Having said that, I don't think that it is the only method of solving this problem (as Cyril stated)
naivecoder

Posted: Fri Jan 13, 2012 12:19 am   Post subject: RE:SPOJ: Prime Generator

hey cyril....
u r saying this prime generator problem can be done through miller-rabin...
miller-rabin:- a^d mod N=1 ..ok?
what if a=61 and d is selected as 99999
given that one is using C or C++??
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 13 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: