Bandwidth Place 2

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!)

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.

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.

Right, that came out wrong. LOL

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?

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

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

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.

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.