How do I compute primes?
If it is not time critical then you could always run through all the numbers in your required range and try to divide them by themselves - the run number ie
check for primes in range 0 to 100
for (int i=0; i<101;i++)
{
for (int j=i-1;j>1;j--)
{
if ((float)(i/j)==(int)(i/j))
{// can divide to a integer
break; //not prime
}
}
}
not fully developed but you get the idea. Only realy suitable if done at initialization time.
Neil
WHATCHA GONNA DO WHEN THE LARGEST ARMS IN THE WORLD RUN WILD ON YOU?!?!
check for primes in range 0 to 100
for (int i=0; i<101;i++)
{
for (int j=i-1;j>1;j--)
{
if ((float)(i/j)==(int)(i/j))
{// can divide to a integer
break; //not prime
}
}
}
not fully developed but you get the idea. Only realy suitable if done at initialization time.
Neil
WHATCHA GONNA DO WHEN THE LARGEST ARMS IN THE WORLD RUN WILD ON YOU?!?!
My guess is that most people hit thier prime right around 28 years old. Probably different for men and women though. I don''t know if thier is a equation to compute this though.
Or you just take an array of numbers, say, 1 thru 10...... and for every number you have a flag (a bool maybe), the flag says wether it's a prime or not.....
To start of you set all the number-flags to true....
Now, for every number in that array you take out the multiples of that number (so, for 2 you take out 4,6,8,10,..... for 3 you take out 6 and 9,..... etc )
1, 2, 3, 5 and 7 are not taken out, those are all the prime-numbers below 10....
I hope this makes any sense at all ........
EDIT: it's called Eratosthenes' something....
----------------------------
"Quotes are cool" - Me
Check out my game Asteroidz, it rules !!!
[edited by - Crawl on April 11, 2002 7:46:47 AM]
To start of you set all the number-flags to true....
Now, for every number in that array you take out the multiples of that number (so, for 2 you take out 4,6,8,10,..... for 3 you take out 6 and 9,..... etc )
...... 2 3 4 5 not taken-out1 12 23 34 *5 56 * *7 78 * *9 *10 * ** = number not a prime (cause it a dividable by any other number than 1 or it self) 1, 2, 3, 5 and 7 are not taken out, those are all the prime-numbers below 10....
I hope this makes any sense at all ........
EDIT: it's called Eratosthenes' something....
----------------------------
"Quotes are cool" - Me
Check out my game Asteroidz, it rules !!!
[edited by - Crawl on April 11, 2002 7:46:47 AM]
I wrote a function for that a while ago....
try %2. if it comes out to be 0, then you''ve saved yourself some work, because it''s not a prime (need a special case for 2 and 3). After that, you can start chugging with divisors to see if it works. The largest divisor you''ll need to test for is the square root of the test number. so you can start your trial divisor at 3, then increment by 2 for each failed test up until the test divisor is >= sqrt(test number)
hope that helps
try %2. if it comes out to be 0, then you''ve saved yourself some work, because it''s not a prime (need a special case for 2 and 3). After that, you can start chugging with divisors to see if it works. The largest divisor you''ll need to test for is the square root of the test number. so you can start your trial divisor at 3, then increment by 2 for each failed test up until the test divisor is >= sqrt(test number)
hope that helps
quote:Original post by Crawl
EDIT: it''s called Eratosthenes'' something....
Yup, the "Sieve of Eratosthenes". Easily found in google or your favorite search engine.
---- --- -- -
Blue programmer needs food badly. Blue programmer is about to die!
You can also take note of the fact that all primes are 6n+/-1 where n is a positive integer except for the first two primes 2 and 3.
Better, I can give a counter example, let n = 31. 6*31 = 186. Now, 185 is divisible by 5 and 37, 187 is divisible by 11 and 17.
I guess it's good in that for all n < 31, one of 6n +/- 1 is prime (but not neccesarily both). And in the little test program I wrote, in the range 1-10,000, only 4,000 or so failed the test. So it's a good way to find candidates perhaps. Not so good as your numbers get bigger, but for small primes it seems to work OK.
Another popular way of finding candidates is using the mercenne formula, which is 2p-1. It can be proved that if 2p-1 is prime, then p is prime. It's not true the other way around, but so far there's been about 39 such primes found (the largest is 213,466,917-1, which is over 4 million digits long!). Of course, it took 100,000 computers over four years to find that candidate (though proving 213,466,917-1 was prime took the winner's 800MHz PC about a week)
PS: I can give you the code for my test program if you're interested. It's in C# though
codeka.com - Just click it.
[edited by - Dean Harding on April 13, 2002 7:34:24 PM]
I guess it's good in that for all n < 31, one of 6n +/- 1 is prime (but not neccesarily both). And in the little test program I wrote, in the range 1-10,000, only 4,000 or so failed the test. So it's a good way to find candidates perhaps. Not so good as your numbers get bigger, but for small primes it seems to work OK.
Another popular way of finding candidates is using the mercenne formula, which is 2p-1. It can be proved that if 2p-1 is prime, then p is prime. It's not true the other way around, but so far there's been about 39 such primes found (the largest is 213,466,917-1, which is over 4 million digits long!). Of course, it took 100,000 computers over four years to find that candidate (though proving 213,466,917-1 was prime took the winner's 800MHz PC about a week)
PS: I can give you the code for my test program if you're interested. It's in C# though
codeka.com - Just click it.
[edited by - Dean Harding on April 13, 2002 7:34:24 PM]
quote:Original post by Dean Harding
Better, I can give a counter example, let n = 31. 6*31 = 186. Now, 185 is divisible by 5 and 37, 187 is divisible by 11 and 17.
I think LilBudyWizer meant that all primes are 6n+/-1 , not that if you take any positive integer and put it into that formula you will get a prime.
I am not sure if this is true, but it sounds like an extension of the fact that every prime execpt 2 has to be an odd number, i.e. 2n+/-1. Using 6 would be including 2 and 3 with only one extra number and narrowing the search field tremendously (well, technically still infinity, but you know what I mean). Perhaps this could be continually extended to include others?
ewen
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
