Programming Forums > Application Development > C++

Ooble · May 19th, 2005, 4:55 PM

Got a link to that?

thomzor · May 20th, 2005, 1:36 AM

heress the link oobliebooblie

http://www.troubleshooters.com/codec...imenumbers.htm

LOI Kratong · May 20th, 2005, 2:12 AM

Hey OOble: i've been to two lectures by him too. i probably should read the book, but the lectures were so interesting!!!

Ooble · May 20th, 2005, 6:08 AM

Thanks for the link, mate. I haven't even started the linked list bit, and it's already down to four seconds! There were two optimisations - I changed the double to an unsigned long long so I could use the modulus operator instead of relying on a function of math.h, and changed i <= sqrt(num) to (i * i) <= num, which is a lot faster.

mackenga · May 20th, 2005, 2:02 PM

Quote:

Originally Posted by brkstf

i could be wrong, but doesn't the "sieve" method require an array of integers the size of the range. for instance, if we wanted to find all primes between 2 and 20, we make an array with 19 members, and we only get eight primes (2, 3, 5, 7, 11, 13, 17, 19) for our memory used. as primes get fewer and farther between, this ratio gets much much worse. the calculation is extremely fast, but the memory overhead is ridiculous.

if you're really into prime numbers, check out the reimann zeta function, which, for no reason any non-mathematician can understand, can predict the nth prime as far as anyone has calculated.

You don't really need an array of integers; an array of bools will do, which can be better, though it slows things down a bit I suppose.

May 19th, 2005, 4:55 PM	#21
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	Got a link to that? __________________ Me :: You :: Them

May 20th, 2005, 2:12 AM	#23
LOI Kratong Professional Programmer Join Date: May 2005 Location: Woo - Boot Sector! Posts: 294 Rep Power: 4	Hey OOble: i've been to two lectures by him too. i probably should read the book, but the lectures were so interesting!!! __________________ www.heldtogether.co.uk

May 20th, 2005, 6:08 AM	#24
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	Thanks for the link, mate. I haven't even started the linked list bit, and it's already down to four seconds! There were two optimisations - I changed the double to an unsigned long long so I could use the modulus operator instead of relying on a function of math.h, and changed i <= sqrt(num) to (i * i) <= num, which is a lot faster. __________________ Me :: You :: Them

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

May 20th, 2005, 1:36 AM	#22
thomzor Newbie Join Date: Apr 2005 Location: The Netherlands Posts: 20 Rep Power: 0	heress the link oobliebooblie http://www.troubleshooters.com/codec...imenumbers.htm

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C++

Prime numbers