Oooh I may have a go at this if i get time. With now being in my final year at uni everything has turned to theory and I want to flex my coding brain again! I was thinking about learning SmallTalk for fun (how normal!) over Christmas so I may do it that. If not I think it will have to be plain old ANSI C.
OCUK Xmas Programming Challenge
- Thread starter tntcoder
- Start date
Associate
2.5Million
And it's less than 3 seconds, it's stage one that takes about 2 of the 3 seconds.
In what language? And using what algorithm (i.e. Lucas-Lehmer etc)? And on the system in your sig? Sorry I'm just sceptical, from memory it takes a few mins to do it in Java (which I'm well aware isn't the most efficient language) - but 3 seconds seems stupidly fast
Soldato
- Joined
- 21 Oct 2009
- Posts
- 2,742
In what language? And using what algorithm (i.e. Lucas-Lehmer etc)? And on the system in your sig? Sorry I'm just sceptical, from memory it takes a few mins to do it in Java (which I'm well aware isn't the most efficient language) - but 3 seconds seems stupidly fast
C++, and yes, computer in sig.
I have no idea what the algorith is tbh, I'd attach the source to prove it, but that'd kinda spoil it for some people
.You know that it just has to calculate how many numbers are prime between 1 and 2.5 million, and not store/print them yeah?
Edit - I'll try and find out what algorithm it is.
Edit again
- sorry, it adds each prime together, not counts them, that was another stage.
Last edited:
Associate
That's not how I read it:
From that, it's got to keep a running total of the sum of the found prime numbers, not just a simple counter?
Associate
Just read your second edit
Soldato
- Joined
- 21 Oct 2009
- Posts
- 2,742
Soldato
- Joined
- 21 Oct 2009
- Posts
- 2,742
I've e-mailed the cpp file to tntcoder, so that he can either confirm what i said is true, or that i've done it all wrong 
(this wouldnt surprise me, although it does seem to give the correct answer at the end ).
(this wouldnt surprise me, although it does seem to give the correct answer at the end ).In what language? And using what algorithm (i.e. Lucas-Lehmer etc)? And on the system in your sig? Sorry I'm just sceptical, from memory it takes a few mins to do it in Java (which I'm well aware isn't the most efficient language) - but 3 seconds seems stupidly fast
Mine takes about a second to do it and that's in Java. As far as I can tell, Lucas-Lehmer is a poor choice for for generating series of primes, as it's designed for testing primality of arbitrary numbers.
In what language? And using what algorithm (i.e. Lucas-Lehmer etc)? And on the system in your sig? Sorry I'm just sceptical, from memory it takes a few mins to do it in Java (which I'm well aware isn't the most efficient language) - but 3 seconds seems stupidly fast
The reason it's quick here is because we are working with small primes. The largest prime under 2.5 mil is 2499997, that's only a 22-bit number. If I asked you to find the sum of the first 2.5 million >= 1024-bit primes, then that's when things would get harder. So it's not too bad computational complexity wise. You can work out if 2499997 is prime in 1582 loop iterations (less with a better algorithm), so if you work out the algorithm complexity for all numbers 2->2.5mil it isn't as bad as you might imagine.
I've e-mailed the cpp file to tntcoder, so that he can either confirm what i said is true, or that i've done it all wrong
(Please just mail to [email protected] as I don't check my hotmail one)
Your code works fine and is correct, nice one
It takes 1.552s on my box, quite impressive! On reflection maybe I should have used larger numbers to make it take longer, will remember that if we ever do this again. I'm going to need a damn accurate timer to do the judging Your prime testing algorithm is also fine, it's the same one I used. Not sure what it's called either, nice and simple though
Sorry it's a long wait till the 28th, I figured it was best to allow time for people to work on it over xmas holidays
Last edited:
Soldato
- Joined
- 21 Oct 2009
- Posts
- 2,742
(Please just mail to [email protected] as I don't check my hotmail one)
Your code works fine and is correct, nice one
Your prime testing algorithm is also fine, it's the same one I used. Not sure what it's called either, nice and simple though
Sorry it's a long wait till the 28th, I figured it was best to allow time for people to work on it over xmas holidays
Ah sorry, i just clicked trust, forgot you put the e-mail address in the op
.NPs about the wait, gives me plenty of time to sort the code out properly
.I'm just downloading Visual Studio now, so may have a go at the challenge at some point this afternoon. If I do, I'll endeavour to do it in C# with some nice parallel linq for you.
Soldato
my brain fried at all the numbers and equations
I would love to give this a go, but the last thing im going to want to do over the xmas break is MORE programming.
Got about a million lines of code to write and debug fully, ready for extremely rigourus testing and it all has to be finished before the new year.
Got about a million lines of code to write and debug fully, ready for extremely rigourus testing and it all has to be finished before the new year.
Why did I choose to do this in C++, the things I could normally do easily in C# have been taken away from me!
I've completed 1,2 & 3 so far and it has a run time of about 1040 milliseconds, just starting to look at 4 if I can work out what the bloody hell a factorial is.
EDIT: Scratch that, 4 done now also, was easy as soon as I understood what a Factorial was
I've completed 1,2 & 3 so far and it has a run time of about 1040 milliseconds, just starting to look at 4 if I can work out what the bloody hell a factorial is.
EDIT: Scratch that, 4 done now also, was easy as soon as I understood what a Factorial was
Last edited:
I joined these forums just for this challenge
Welcome, thanks for having a go!Rjindael is a nice cipher
Soldato
Nice idea, hopefully I can find the time to get an entry in.
I have just finished all the steps.
It took my implementation 2.7 seconds to complete the full program with 1.7 seconds of that to find the 2.5 million prime numbers. This is running on a Q6600 @ 3.4GHz.
Quite happy with it but it needs some major tidying up, stage 2 looks terrible
It took my implementation 2.7 seconds to complete the full program with 1.7 seconds of that to find the 2.5 million prime numbers. This is running on a Q6600 @ 3.4GHz.
Quite happy with it but it needs some major tidying up, stage 2 looks terrible