Login or Sign Up to become a member!
LessThanDot Site Logo

LessThanDot

A Technical Community for IT Professionals

Less Than Dot is a community of passionate IT professionals and enthusiasts dedicated to sharing technical knowledge, experience, and assistance. Inside you will find reference materials, interesting technical discussions, and expert tips and commentary. Once you register for an account you will have immediate access to the forums and all past articles and commentaries.

LTD Social Sitings

Lessthandot twitter Lessthandot Linkedin Lessthandot facebook Lessthandot rss

Note: Watch for social icons on posts by your favorite authors to follow their postings on these and other social sites.

Highly Rated Users

Forum
No Posts Rated

Top 50
Given
Received

Forum Statistics

Users
Members:
1592
Members Online:
3
Guests Online:
7

Total Post History
Posts:
80552
Topics:
18446

7-Day Post History
New Posts:
9
New Topics:
1
Active Topics:
7

Our newest member
marykee

Other

FAQ
All times are UTC [ DST ]

Google Ads

LTD Puzzle 4: Finding Prime Numbers

Mind Boggling Puzzles, to keep that grey matter in shape...
Forum rules
Always post answers in a "Hidecode" tag, so that others have a chance to answer the question too.
Please wait...

LTD Puzzle 4: Finding Prime Numbers

Postby damber on Fri Jun 27, 2008 3:52 pm

This weeks puzzle is quite straight forward.

All we want you to do is find every prime number between 0 and 1,000,000. That's it. :-)

A prime number is a number that can only be divided by itself and 1 to result in a whole number. E.g. 2, 3 and 5 are all prime, but 4 can be divided by 2 aswell as 4 and 1, so it is not.

The faster your code is, the better - so if you were thinking of looping through each number, that may not be the most efficient route... ;-)

For extra points, find the Mersenne primes too.

For even more extra points we challenge you to find all the primes between 0 and 10,000,000. And for those hardcore geeks - how about 0 to 2,147,483,647 (the maximum for a 32 bit integer).

Good luck...
a smile is worth a thousand kind words, so smile, it's easy! :-)


CODE: $5
WORKING CODE: $500
PROPERLY DESIGNED & WORKING CODE: Priceless
User avatar
damber
LTD Admin
LTD Admin
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
 
Posts: 3134
Joined: Tue Oct 09, 2007 1:48 pm
Location: North Wales, UK
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby MrChaos on Mon Jun 30, 2008 8:56 pm

Ugle C code but, it should work.
Code is hidden, SHOW
MrChaos
Newbie
Newbie
LTD Bronze - Rating: 11
 
Posts: 1
Joined: Mon Jun 30, 2008 8:52 pm

Re: LTD Puzzle 4: Finding Prime Numbers

Postby damber on Mon Jun 30, 2008 9:48 pm

Well done to MrChaos for getting the first (and quick) answer in !

Just in case you were all wondering what the highest prime number was, AlexCuse has already posted that answer here: Topic1983: The Highest Prime Number in the World
a smile is worth a thousand kind words, so smile, it's easy! :-)


CODE: $5
WORKING CODE: $500
PROPERLY DESIGNED & WORKING CODE: Priceless
User avatar
damber
LTD Admin
LTD Admin
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
 
Posts: 3134
Joined: Tue Oct 09, 2007 1:48 pm
Location: North Wales, UK
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby AlexCuse on Mon Jun 30, 2008 9:52 pm

Yes, thank you Mr. Chaos, was not expecting to see much C on here. A most pleasant surprise.

damber, the veracity of that claim has come into dispute. Maybe those crazy mathematicians are right and we'll never know the highest prime number ;)
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5411
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby Emtucifor on Mon Jun 30, 2008 9:53 pm

The highest prime number is infinitely high!

There is only the highest prime number man has identified/proven so far.
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby traingamer on Mon Jun 30, 2008 10:08 pm

I found a spiffy, easily modified online JavaScript example based on the Sieve of Erastoshenes, but I haven't gotten around to modifying it in VBA (or any other language). Maybe tonight.
Greg

People demand freedom of speech as a compensation for the freedom of thought which they seldom use. Kierkegaard
User avatar
traingamer
Senior Sage
Senior Sage
LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233
 
Posts: 1487
Joined: Thu Feb 28, 2008 4:13 pm
Location: St. Louis, MO, US
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby SQLDenis on Mon Jun 30, 2008 10:10 pm

I know at least 2 people who have a Sieve of Erastoshenes SQL version
User avatar
SQLDenis
LTD Admin
LTD Admin
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
 
Posts: 21757
Joined: Wed Oct 10, 2007 6:43 pm
Location: Princeton, New Jersey, USA,World, Solar System, Milky Way, Universe and Beyond
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby damber on Mon Jun 30, 2008 10:27 pm

Erik wrote:The highest prime number is infinitely high!


Erik,
You should probably check out the link, and I think you'll agree that that's the highest prime number in the world... ;-) Denis tried to offer another possible highest prime, but lost out on a technicality... :-P

traingamer, SQLDenis, - only original code please - otherwise where's the fun/challenge ? :-)
a smile is worth a thousand kind words, so smile, it's easy! :-)


CODE: $5
WORKING CODE: $500
PROPERLY DESIGNED & WORKING CODE: Priceless
User avatar
damber
LTD Admin
LTD Admin
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
 
Posts: 3134
Joined: Tue Oct 09, 2007 1:48 pm
Location: North Wales, UK
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby Emtucifor on Mon Jun 30, 2008 10:34 pm

Should we get more/less points for not using/using someone else's code as a starting place?

Programming the puzzle from scratch is a different task than porting another's code, though if you get stuck I'd say that looking at other code is legitimate...
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby SQLDenis on Mon Jun 30, 2008 10:51 pm

damber wrote:traingamer, SQLDenis, - only original code please - otherwise where's the fun/challenge ? :-)



I will not post the code, hopefully they will :-)
User avatar
SQLDenis
LTD Admin
LTD Admin
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
LTD Gold - Rating: 3455LTD Gold - Rating: 3455LTD Gold - Rating: 3455
 
Posts: 21757
Joined: Wed Oct 10, 2007 6:43 pm
Location: Princeton, New Jersey, USA,World, Solar System, Milky Way, Universe and Beyond
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby Emtucifor on Tue Jul 01, 2008 3:12 am

Here's an HTML/javascript version (yes, I know, funny). It doesn't perform too well. Even in Firefox you have to tell it to continue 3 times to calculate just 1 million of them.

I like this code because I didn't give it any seed numbers at all, not even the sieve list. The sieve size is not hardcoded, though this code can only handle sieve sizes of 1-3 because 4 comes out to 48 members in the sieve list and that's too many bits for storing the value as a long integer. I wrote this all from scratch.

I'd like to rewrite this code using C++ or even assembler, with some libraries for doing math on very large numbers. It would be cool to do a sort of sliding sieve: storage becomes a real problem when dealing with large quantities of primes, and with a sieve you get a fairly decent storage algorithm with 1 bit per candidate, though of course it becomes very sparse when you get to high numbers. So the sliding sieve would stairstep into the next size as it went along, conserving storage space at the expense of some CPU, but with a real tradeoff of checking fewer numbers along the way.

There are other optimizations besides the sieve that could be done. I'd love to have the time and energy to learn more about them and write code that actually uses them.

This program has a bug in that it may display a few more numbers than you asked for (though it calculates the primes correctly). I don't have time to fix it right now...

Code is hidden, SHOW

P.S. Damber, I have an idea for a puzzle some week: create your own functions to add, subtract, divide, multiply, and calculate power and log for numbers up to 1000 digits (or some other huge value).
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA

Re: LTD Puzzle 4: Finding Prime Numbers

Postby spoulson on Tue Jul 01, 2008 2:50 pm

MrChaos wrote:Ugle C code but, it should work.


I like the code, but unfortunately it's not completely copy/paste. Visual C++ 2008 complains of a couple points. It didn't like the huge static size on primes[] and threw a stack overflow. I replaced it with a pointer and a malloc() call. Also, in C, you can't intermix declaration lines with code, so the "primes[0] = 2" had to be moved down below the decls.

Overall, it works great! Thanks for the submission.
User avatar
spoulson
Senior Apprentice
Senior Apprentice
LTD Bronze - Rating: 115LTD Bronze - Rating: 115LTD Bronze - Rating: 115
 
Posts: 205
Joined: Mon Jun 02, 2008 2:37 am
Location: Middletown, DE, USA
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby traingamer on Tue Jul 01, 2008 4:15 pm

When I said modifying it, I meant the sieve, not the JavaScript code. :blush: :D
Greg

People demand freedom of speech as a compensation for the freedom of thought which they seldom use. Kierkegaard
User avatar
traingamer
Senior Sage
Senior Sage
LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233LTD Bronze - Rating: 233
 
Posts: 1487
Joined: Thu Feb 28, 2008 4:13 pm
Location: St. Louis, MO, US
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby Emtucifor on Tue Jul 01, 2008 11:21 pm

Oops... I hardcoded the Mersenne prime seed number. A fix:

Code is hidden, SHOW
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby AlexCuse on Thu Jul 03, 2008 1:19 pm

I had WAY too much fun with this one. I must have tried at least 10 different ways of doing it in F#. Here's what I came up with in the end. While its slower than what I had in C#, I find it aesthetically pleasing. Finds all primes up to 2147483616 (the max capacity of the data structure I chose, even though it is initialized with an int32!) in about ten minutes:

Code is hidden, SHOW


However, I'm not sure if it is because of my lack of skill in F#, or because the F# compiler doesn't have as many years of wisdom as C#'s, but I was able to do much better in C# using the same method (minus the recursion, which seemed to actually make it slower). I had a really cool solution that returned an IEnumerable, but this seemed to get bogged down in the higher numbers. Using a similar method to the one used in F# could find all the primes to 2147483616 in 4:27 on my laptop (with everything coded in main), but I wanted to find as high as I could. This led me to some guy's own implementation of BitArray (http://www.jaggersoft.com/csharp_standard/17.8.htm), which does offer the size advertised. Its' a bit slower, but I thought it beat writing a ton of extra code to work with an "overflow" BitArray.

So, here's the BitArray2 class:
Code is hidden, SHOW


And the "sledgehammer" method of getting the primes (I added int32.maxvalue at the end only if that's the capacity given, because we know that's prime and it is JUST out of reach). I'm not sure if the try/catch works any faster than checking the values prior to assignment, but I would imagine it does (i'm out of time for testing). This saves us from having to check for values <0 in the outer loop as well (since if you try to add past int32.maxvalue you get a negative #).

Time for this (with checking the values twice on each loop iteration) was 5:46. Hoping to have a test with the try/catch done running by the time I type the rest of this.

Code is hidden, SHOW


Times for the C# methods include querying the list to get Min and Max values as well as count (which is no trivial task when you're working with such a long list). And, handling the exceptions was slightly faster than preventing them at 5:29
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5411
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US

Re: LTD Puzzle 4: Finding Prime Numbers

Postby Emtucifor on Thu Jul 03, 2008 6:41 pm

And a fix for my "sometimes it displays more numbers than you asked for":

Code is hidden, SHOW

I needed to use sieve[i] instead of i.
God cries a little bit every time someone builds a database.
User avatar
Emtucifor
Guru
Guru
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030LTD Gold - Rating: 1030
LTD Gold - Rating: 1030
 
Posts: 2835
Joined: Fri May 30, 2008 9:30 pm
Location: Bellingham, WA
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby damber on Sun Jul 06, 2008 1:47 pm

Erirk wrote:P.S. Damber, I have an idea for a puzzle some week: create your own functions to add, subtract, divide, multiply, and calculate power and log for numbers up to 1000 digits (or some other huge value).


Thanks Erirk - I've added it to our list of puzzle questions - so look out for it over the next few weeks ;-)
a smile is worth a thousand kind words, so smile, it's easy! :-)


CODE: $5
WORKING CODE: $500
PROPERLY DESIGNED & WORKING CODE: Priceless
User avatar
damber
LTD Admin
LTD Admin
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660LTD Silver - Rating: 660
 
Posts: 3134
Joined: Tue Oct 09, 2007 1:48 pm
Location: North Wales, UK
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby chrissie1 on Sat Jul 12, 2008 9:06 am

There are 2 types of winner - a "People's Champion" (the one with the most rating points across all their posts) and the LTD Admin's Champion (selected with our special formula....honest...well, maybe it's just the ones that the admins thought were particularly good :-))

So...

People's Champion: MrChaos scoring 11 points

LTD Admin's Champion: AlexCuse for usinf F#.


Congratulations to all.. and good luck on next weeks puzzle :-)
pink fuzzy slippers
User avatar
chrissie1
Senior Guru
Senior Guru
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088LTD Gold - Rating: 2088
LTD Gold - Rating: 2088LTD Gold - Rating: 2088
 
Posts: 9348
Joined: Wed Oct 10, 2007 7:18 pm
Location: Belgium
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby tisodotsk on Fri Aug 08, 2008 10:23 pm

My solution in PHP:
Code is hidden, SHOW

I use some optimizations.
Output:
  1. Prime numbers less than milion: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ...
  2. ...
  3. End, 78498 prime numbers founded
  4. Mersenne prime numbers: 3, 7, 31, 127, 8191, 131071, 524287
I try to improve my English language skills. Most things i do better than this.
tisodotsk
Apprentice
Apprentice
LTD Bronze - Rating: 62LTD Bronze - Rating: 62
 
Posts: 22
Joined: Fri Aug 08, 2008 12:45 pm
Location: Bratislava, Slovakia

Re: LTD Puzzle 4: Finding Prime Numbers

Postby Hazar on Sat Aug 16, 2008 9:04 am

my simple C++ solution:

Code is hidden, SHOW
Hazar
Newbie
Newbie
LTD Bronze - Rating: 6
 
Posts: 1
Joined: Sat Aug 16, 2008 9:00 am

Re: LTD Puzzle 4: Finding Prime Numbers

Postby AlexCuse on Sat Aug 16, 2008 2:19 pm

Excellent Hazar. In the future could you please use the "hidecode" tag on your answers (only in the puzzle forum of course!)

You've just given me an idea too. :)
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5411
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby GothGargoyle on Wed Mar 04, 2009 8:37 pm

Here's a version in Java. On my machine it determined the primes < 2,147,483,647 in 2 minutes 16 seconds.

It is based on the Sieve of Eratosthenes algorithm, and uses a BitSet for minimizing the amount of memory required.

Code is hidden, SHOW
Last edited by GothGargoyle on Wed Mar 04, 2009 10:47 pm, edited 1 time in total.
GothGargoyle
Apprentice
Apprentice
LTD Bronze - Rating: 18
 
Posts: 5
Joined: Wed Mar 04, 2009 8:31 pm

Re: LTD Puzzle 4: Finding Prime Numbers

Postby AlexCuse on Wed Mar 04, 2009 9:16 pm

That's a pretty slick one GothGargoyle. Very clean and easy to read.
Say what you like about the tenets of National Socialism Dude, at least it's an ethos
User avatar
AlexCuse
LTD Admin
LTD Admin
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021LTD Gold - Rating: 1021
LTD Gold - Rating: 1021
 
Posts: 5411
Joined: Tue Oct 09, 2007 5:26 pm
Location: Pennsylvania, US
Unrated

Re: LTD Puzzle 4: Finding Prime Numbers

Postby ReaperUnreal on Sun Jan 08, 2012 2:51 am

I love prime number finding, it's fun and a good way to learn new languages. Today I decided to focus on algorithms instead of language and did it in a language I'm familiar with, C++.

I've got 3 separate implementations here, all using an std::bitvector to save memory. I've tested with an array and this is faster when you're using bigger numbers by a large margin.

I'll just quickly go over the 3 implementations.
1. Trial Division, the slowest way to find out if a number is prime. You divide by all the numbers smaller than it.

2. Sieve of Erastothenes, a lot of people here have used it and it's a good one to do. This has the extra optimizations of starting marking off numbers at p^2 instead of 2p, and it searches for all filters below sqrt(max).

3. Sieve of Atkin, this is a modern version of the Sieve of Erastothenes which does some filtering work up front so that it only has to mark off the squares of primes in the actual sieving step. The math for why this works is pretty involved, so I won't explain it here. Also I barely remember anything from that class.

So, here's the code:
Code is hidden, SHOW


Fair warning, this was written for Windows/MSVC, so some simple things (like __int64) would have to be changed on other platforms.

I didn't bother timing the trial division algorithm because it's way too slow, but here's the output:
Using the Sieve of Erastothenes method
Elapsed Time for all primes less than 2147483647: 87100ms
Using the Sieve of Atkins method
Elapsed Time for all primes less than 2147483647: 63755ms

Not bad, I reckon.
ReaperUnreal
Newbie
Newbie
LTD Bronze - Rating: 13
 
Posts: 2
Joined: Tue Jan 03, 2012 7:58 pm