Calculating prime numbers..

Message

#1 Post by **palmboy5** » Mon Oct 15, 2007 11:47 pm

I had to write a program that would calculate all prime numbers within one million and show them on the screen. That part is easy, but it takes 53 seconds to process on my Pentium M 1.6GHz. How mine calculates is to test every number from 1 to 1,000,000 if they're divisible by any of the prime numbers smaller than them or not. Of course in that sense, its dividing up to the prime number 5 when testing the number 6. Obviously that would never need to be tested. Anyway, to bring that to a larger scale:

What I've found is that of the 78498 primes in one million, you only need to test up to the 1009th prime. I'm not sure which one is the minimum, but its within that range. In other words, the number 999,999 or w/e will never be tested for divisibility by beyond the 1009th prime. The output is still correct, no extra non-primes appear from this lack of tests.

Anyone know why this is? >_<

(Only testing up to the 1009h prime cuts the calculation time down to 2 seconds wooooot!)

2005 · #2 Post by **2005** » Tue Oct 16, 2007 3:53 pm

Why write the program like that? The system has to check every prime number before the one your on to see if it fits into the number in question. As you discover more and more primes you get more and more checks.

Why not just check every number from 1 to 1 million if its divisible by itself or 1. A much simpler and more efficent program.

#3 Post by **palmboy5** » Tue Oct 16, 2007 11:39 pm

Then every number would register as a prime number... every numbers going to be divisible by 1 or itself.

Yes I know it gets hectic to check all the prime numbers, but what I've found is that I only need to test up to the 1009th prime for all the rest of the primes up to 1 million. There must be some mathematical reason that within the numbers 1 and 1 million, only up to the 1009th prime is needed.

2005 · #4 Post by **2005** » Wed Oct 17, 2007 8:01 am

Right, that came out wrong. LOL

#5 Post by **palmboy5** » Wed Oct 17, 2007 3:04 pm

LOL Yes. For the hell of it, I actually tried to make the program do that. IT CAN COUNT TO ONE MILLION FASTER THAN YOU, NOOB! It kept crashing o-o too pro for me. Maybe the int datatype can't handle a number of that size? EDIT: No I got it now lol, wooo..

Finally went and checked, the 1009th prime number is 7907. So why is this number the highest number I'll need to check divisibility of all other prime numbers up to 1 million?

2005 · #6 Post by **2005** » Wed Oct 17, 2007 7:19 pm

maybe all other prime numbers are just products of other primes?

#7 Post by **palmboy5** » Thu Oct 18, 2007 7:42 pm

Dude... if dragon had a functioning computer and could visit right now... He would be laughing his ass off.

2005 · #8 Post by **2005** » Sat Oct 20, 2007 12:58 am

2005 wrote:maybe all other prime numbers are just products of other primes?

Lolz, I hope you didn't take that seriously....

anyhow, have you gotten any further with this. I haven't had time to sit and try to write up the program and see why you don't need any primes past that one.

#9 Post by **palmboy5** » Sat Oct 20, 2007 8:37 pm

No I haven't lol.. just my dad telling me I should only need to test up to the prime number below the sqrt of the test's max (1 mil here). That of which is 997 instead of what I found, 7079. If I try to test any lower than 7079 my output will be wrong. False primes.