Prime number generation???

[timeshifter]

I have been working at a formula, be it a straight function or a recursive formula, that given n, will generate the nth prime number. Thus far I have had little luck, and I tried Google, but haven't found anything there.

Does anyone know where I can find a formula or set of formulas to solve my problem???

[manavo11]

Our first contest was Prime Number generation : http://www.vbforums.com/forumdisplay.php?f=68

[NoteMe]

You have to run through them all. At this date there is no other 100% safe way to detect if a number is prime then to factorize (SP?) it.



ØØ

[timeshifter]

I really hate factoring numbers...

[NoteMe]

It isn't that hard. just do a loop. First test if you can devide it on 2, and see if how many times you can do it. When you have done that, then test 3. As many times as that work. And then just add 2, so you will test on 5, 7, 9 and so on.




ØØ

[wossname]

It isn't that hard. just do a loop. First test if you can devide it on 2, and see if how many times you can do it. When you have done that, then test 3. As many times as that work. And then just add 2, so you will test on 5, 7, 9 and so on.

ØØ

It would be much faster to test a number against all the primes less than sqrt(number). Since the numbers are being generated on the fly anyway you might as well use them to test future primes. This system does work because I wrote a program on it a few years back.

For example you test 19 against 2 and 3, (NOT 5, 7, 11, 13 and 17 because they are all GREATER than sqrt(19). Since it is not divisable by 2 or 3 then it must be prime. Testing 20 against 2 would fail instantly because 2 is a factor of 20, thus 20 is not prime.

[NoteMe]

Sure, and there is a lot of other things you can speed up too. Just look at my code in the contest section. I just tried not to confuse him too much with all the stuff I have done there...




ØØ