20 users logged in
Proud partner of GDC 2025
Before posting, review our community guidelines.
Support GameDev.net with a monthly GDNet+ subscription!
How do I compute primes?
491
April 15, 2002 04:26 PM
Actually you only need to check primes less than the square root. If there is a factor greater than the square root then there is also a factor less than the square root. You only need to find that there is a factor, not what all the factors are.
Keys to success: Ability, ambition and opportunity.
122
April 15, 2002 04:36 PM
java program to compute all prime numbers below a number entered on the comand-line.
To the vast majority of mankind, nothing is more agreeable than to escape the need for mental exertion... To most people, nothing is more troublesome than the effort of thinking.
/***** [file] - test.java.** [desc] - test program.** [date] - 12/3/2001.** [auth] - Drew Joaquin.***//* import classes. */import java.awt.*;import java.io.*;/* test class definition. */public class test { // main entry point. public static void main(String sCmd[]) { boolean bIsPrime; int i, k, n, prime; BufferedReader brReader; String sInput; try { brReader = new BufferedReader(new InputStreamReader(System.in)); // query the user for a number. System.out.print("Please, enter a number: "); sInput = brReader.readLine(); n = Integer.parseInt(sInput); // assuming user inputs a number, else exception. for (k = 2; k < n; k++) { /* assume the number is a prime number. */ prime = (test.power(2, k) - 1); bIsPrime = true; for (i = 2; i < (prime - 1); i++) { if ((prime % i) == 0) { /* "prime" is not a prime number. */ bIsPrime = false; i = (prime - 1); } } if (bIsPrime) { /* calculate the perfect number. */ prime *= test.power(2, (k - 1)); if (prime < n) System.out.println(prime); else k = (n - 1); } else if (prime >= n) k = (n - 1); } } } // calculates "x" to the power of "y". public static int power(int x, int y) { int ret = 1; for (int i = 1; i <= y; i++) ret *= x; return (ret); }} To the vast majority of mankind, nothing is more agreeable than to escape the need for mental exertion... To most people, nothing is more troublesome than the effort of thinking.
To the vast majority of mankind, nothing is more agreeable than to escape the need for mental exertion... To most people, nothing is more troublesome than the effort of thinking.
122
April 16, 2002 01:07 PM
quote:
Original post by LilBudyWizer
Actually you only need to check primes less than the square root. If there is a factor greater than the square root then there is also a factor less than the square root. You only need to find that there is a factor, not what all the factors are.
Oh, yeah, I think that''s what I meant
WNDCLASSEX Reality;
...
...
Reality.lpfnWndProc=ComputerGames;
...
...
RegisterClassEx(&Reality);
Unable to register Reality...what''s wrong?
---------
Dan Upton
http://0to1.org
http://www20.brinkster.com/draqza
AIM: DigytalSpyder
WNDCLASSEX Reality;......Reality.lpfnWndProc=ComputerGames;......RegisterClassEx(&Reality);Unable to register Reality...what's wrong?---------Dan Uptonhttp://0to1.orghttp://www20.brinkster.com/draqza
122
April 19, 2002 02:44 AM
Computing primes is hideously expensive. It''s actually NP-complete, which means we think it can''t be done in polynomial time (i.e., it''s slow).
So if you just need some primes to use in a game, or something, just use a precomputed table. There''s a good list of small primes at http://www.utm.edu/research/primes/
Of course, studying primes and number theory is pretty cool, so I can completely understand if you''re interested in computing primes for more academic reasons.
I''ve got a printout of a formula that''s supposed to "generate" primes. I forget exactly how it works, but it had something like 23 or 24 variables. Apparently, if you plug in values for all the variables and you get a positive result, then the result is prime. (Of course, actually getting a positive result is rare, so it''s not an efficient prime-computing method.)
I''ll see if I can find the printout, but if anyone else knows the formula in question, I''d appreciate a link to it...
So if you just need some primes to use in a game, or something, just use a precomputed table. There''s a good list of small primes at http://www.utm.edu/research/primes/
Of course, studying primes and number theory is pretty cool, so I can completely understand if you''re interested in computing primes for more academic reasons.
I''ve got a printout of a formula that''s supposed to "generate" primes. I forget exactly how it works, but it had something like 23 or 24 variables. Apparently, if you plug in values for all the variables and you get a positive result, then the result is prime. (Of course, actually getting a positive result is rare, so it''s not an efficient prime-computing method.)
I''ll see if I can find the printout, but if anyone else knows the formula in question, I''d appreciate a link to it...
122
April 19, 2002 03:03 AM
I'm following up on my own post...
I did a quick internet search, and I found a FAQ that mentions the formula in question. From http://www.cs.unb.ca/~alopez-o/math-faq/node36.html:
It doesn't list the formula, unfortunately.
[edited by - ijprest on April 19, 2002 4:05:17 AM]
I did a quick internet search, and I found a FAQ that mentions the formula in question. From http://www.cs.unb.ca/~alopez-o/math-faq/node36.html:
quote:
There is no polynomial which gives all the prime numbers. This is a simple exercise to prove.
There is no non-constant polynomial that only takes on prime values. The proof is simple enough that an high school student could probably discover it. See, for example, Ribenboim's book The Book of Prime Number Records.
Note, however, by the work of Jones, Sato, Wada, and Wiens, there is a polynomial in 26 variables such that the set of primes coincides with the set of positive values taken by this polynomial. See Ribenboim, pp. 147-150.
It doesn't list the formula, unfortunately.
[edited by - ijprest on April 19, 2002 4:05:17 AM]
175
April 19, 2002 12:27 PM
you mean this one??
http://primes.utm.edu/glossary/page.php/MatijasevicPoly.html
did a quick saerch - this one is much neater, but in german.
http://www.turing-maschine.de/daten/mathematic/beweise/primenumbers-jsww.html
Beer - the love catalyst
good ol' homepage
[edited by - Dredge-Master on April 19, 2002 1:29:16 PM]
http://primes.utm.edu/glossary/page.php/MatijasevicPoly.html
did a quick saerch - this one is much neater, but in german.
http://www.turing-maschine.de/daten/mathematic/beweise/primenumbers-jsww.html
Beer - the love catalyst
good ol' homepage
[edited by - Dredge-Master on April 19, 2002 1:29:16 PM]
Beer - the love catalystgood ol' homepage
April 22, 2002 05:43 AM
You could also use a randomised algorithm to get check probable primes. If you search for keywords "monte-carlo", "algorithm" and "prime" you should get something useful. If I remember correctly, it takes surprisingly few iterations ( ~50 ) to check that a given number is prime with such a high probability that you are more likely to get a wrong result due to cosmic rays flipping values on your CPU.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
Recommended Tutorials
Advertisement