prime number question
Author
say u have a loop from 0-10
how do u go about checking to see which ones are prime numbers?
using mod is confusing me
You try dividing the prospective prime by all it''s possible divisors, and see if any leave a zero remainder. (Modulus is the remainder function) 7 mod 2 is 1 because 7 divided by 2 has a remainder of 1.
If nothing divides it evenly, it''s a prime number.
If nothing divides it evenly, it''s a prime number.
Author
so if i have like 7
do i do a loop that does the following
7%1 7%2 7%3 7%4 7%5 7%6 7%7
and check if its remainder is 0?
do i do a loop that does the following
7%1 7%2 7%3 7%4 7%5 7%6 7%7
and check if its remainder is 0?
quote:Original post by omegasyphon
so if i have like 7
do i do a loop that does the following
7%1 7%2 7%3 7%4 7%5 7%6 7%7
and check if its remainder is 0?
Yes, but 7%1 and 7%7 don''t count, according to the defintion of prime numbers.
And if you think about it a little bit, you''ll realize that you really only have to check half of those numbers.
really, your prime number list kindof feeds off of itself. To figure out if a number is prime you run through combos of x%n. x is your number and n is all the prime numbers before x.
I had a program once that needed an array of something like the first 100 prime numbers. Instead of calculating the table everytime I needed it, I made a nother program that calculated the primes and printed them out with array indexes so that all I had to do was cut and paste the array into my code from my output.
AOL, so easy to use, no wonder it''s nothing but a bunch of retards
Spyder''s Web Games
I had a program once that needed an array of something like the first 100 prime numbers. Instead of calculating the table everytime I needed it, I made a nother program that calculated the primes and printed them out with array indexes so that all I had to do was cut and paste the array into my code from my output.
AOL, so easy to use, no wonder it''s nothing but a bunch of retards
Spyder''s Web Games
quote:Original post by capn_midnight
really, your prime number list kindof feeds off of itself. To figure out if a number is prime you run through combos of x%n. x is your number and n is all the prime numbers before x.
All the prime numbers before x that are less than or equal to sqrt(x) if you''re speed conscious.
Hmm...
Lets say you want to check if 100 is prime.
Firstly, we can state a general rule: if x is divisible by y, then x is divisible by x/y.
Which is to say: if 100 is divisible by 2, then it is also divisible by 100/2. 100 is divisible by 2 - the result is 50. 100 is also divisible by 50, and the rsuilt, of course, is 2.
Another rule we can state is: if x is not divisible by y, then x is not by any multiple of y.
Because 100 is not divisible by 3, it is not divisble by any multiple of 3.
We can use this to speed up our prime tests: first, test to see if x is divisible by 2. If it is, then x is not prime. If it is not, then we know that it is not divisible by any multiple of two. Immediately, we have halved the number of checks that need to be performed to determine if x is prime. Now, if x is divisible by 3, then it is not prime. If it is not divisible by 3, then it is not divisible by any multiple of 3. Now we have excluded one third of the remaining tests. The next number is 4. Because 4 is a multiple of 2, we don't need to
check if x is divisible by it - we know that it isn't.
Going up, we check against 2, 3, 5, 7, 11, 13, 17... There is a pattern here - all of these tests are against primes. So, to determine if a number is prime, we only need to test if it is divisble by another prime - if it is, then it isn't prime itself.
However, how many numbers to test? Clearly, 100 cannot divied evenly into any number greater than 100, so we know that we could try all the primes between 2 and 99.
However, rule one proves that divisors always come in pairs: 50,2; 20,5; 25,4. These pairs always produce 100, and from this we can infer another rule: for a pair of divisors of x, (a,b), the following rule holds: ((a < sqr(x)) and (b > sqr(x))) or ((a > sqr(x)) and (b < sqr(x))) or ((a == sqr(x)) and (b == sqr(x))) . This makes sense: the product of two numbers less then the square of x must be less than x: 9x9 = 81; the produce of two numbers greater than the square of x must be more than x: 11x11 = 121. So, either one must be greater and one lesser than the square, or they must both be equal to the square.
The square of 100 is 10. We know that if 100 is not divisible by any number between 2 and 10, then 100 is prime - if it isn't divisible by any number between 2 and 10, it can't be divisible by any number between 11 and 99. And we only need to check primes: between 2 and 10 there are four primes. (2, 3, 5, 7) So, our test for the primeness of 100 has been reduced t testing 98 numbers (2 to 99) to testing only four.
This method of speeding the testing of primes is known as the Seive Of Eratosthenes . It allows you to determine the primeness of quite large numbers very quickly. For example, you can use it to determine if a number between 1 and 160,000 is prime with a maximum of 70 tests.
You can find info about the Sieve, and primes in general at http://www.utm.edu/research/primes/programs/Eratosthenes/.
Signatures? We don't need no steenking signatures!
Edit: Mis-spelt the Greek dude's name.
Edited by - Mayrel on November 1, 2001 12:28:14 PM
Lets say you want to check if 100 is prime.
Firstly, we can state a general rule: if x is divisible by y, then x is divisible by x/y.
Which is to say: if 100 is divisible by 2, then it is also divisible by 100/2. 100 is divisible by 2 - the result is 50. 100 is also divisible by 50, and the rsuilt, of course, is 2.
Another rule we can state is: if x is not divisible by y, then x is not by any multiple of y.
Because 100 is not divisible by 3, it is not divisble by any multiple of 3.
We can use this to speed up our prime tests: first, test to see if x is divisible by 2. If it is, then x is not prime. If it is not, then we know that it is not divisible by any multiple of two. Immediately, we have halved the number of checks that need to be performed to determine if x is prime. Now, if x is divisible by 3, then it is not prime. If it is not divisible by 3, then it is not divisible by any multiple of 3. Now we have excluded one third of the remaining tests. The next number is 4. Because 4 is a multiple of 2, we don't need to
check if x is divisible by it - we know that it isn't.
Going up, we check against 2, 3, 5, 7, 11, 13, 17... There is a pattern here - all of these tests are against primes. So, to determine if a number is prime, we only need to test if it is divisble by another prime - if it is, then it isn't prime itself.
However, how many numbers to test? Clearly, 100 cannot divied evenly into any number greater than 100, so we know that we could try all the primes between 2 and 99.
However, rule one proves that divisors always come in pairs: 50,2; 20,5; 25,4. These pairs always produce 100, and from this we can infer another rule: for a pair of divisors of x, (a,b), the following rule holds: ((a < sqr(x)) and (b > sqr(x))) or ((a > sqr(x)) and (b < sqr(x))) or ((a == sqr(x)) and (b == sqr(x))) . This makes sense: the product of two numbers less then the square of x must be less than x: 9x9 = 81; the produce of two numbers greater than the square of x must be more than x: 11x11 = 121. So, either one must be greater and one lesser than the square, or they must both be equal to the square.
The square of 100 is 10. We know that if 100 is not divisible by any number between 2 and 10, then 100 is prime - if it isn't divisible by any number between 2 and 10, it can't be divisible by any number between 11 and 99. And we only need to check primes: between 2 and 10 there are four primes. (2, 3, 5, 7) So, our test for the primeness of 100 has been reduced t testing 98 numbers (2 to 99) to testing only four.
This method of speeding the testing of primes is known as the Seive Of Eratosthenes . It allows you to determine the primeness of quite large numbers very quickly. For example, you can use it to determine if a number between 1 and 160,000 is prime with a maximum of 70 tests.
You can find info about the Sieve, and primes in general at http://www.utm.edu/research/primes/programs/Eratosthenes/.
Signatures? We don't need no steenking signatures!
Edit: Mis-spelt the Greek dude's name.
Edited by - Mayrel on November 1, 2001 12:28:14 PM
Fellas, the guy just wants a simple function to check if it's prime or not.
Here's a simple function to do that.
Of course you don't have to go all the way to the value, you could stop at iValue/2 + 1, but it's a generic and easy to understand function.
Nutts
Edited by - BeerNutts on November 1, 2001 2:01:33 PM
Here's a simple function to do that.
BOOL IsPrime(int iValue){ int iModNum; BOOL bPrime = FALSE; // granted iValue is grater then 2 for (iModNum = 2; iModNum < iValue; iModNum++) { if (iValue%iModNum == 0) { bPrime = TRUE; break; } } return (bPrime);} Of course you don't have to go all the way to the value, you could stop at iValue/2 + 1, but it's a generic and easy to understand function.
Nutts
Edited by - BeerNutts on November 1, 2001 2:01:33 PM
'Nutts, I think that function has a bug. The line
checks if the number is divisible (it would return true for iValue = 6 and iModNum = 2, and would therefore say 6 was prime - which it most definitely isn't!)
Here's what I think you meant to so:
EDIT:
Of course, this method is inefficient in very large iterations. A much better method for determining all prime numbers up to an arbitrarily large limit is to use the Sieve of Eratosthenes and bitsets.
Edited by - Oluseyi on November 1, 2001 2:12:24 PM
if(iValue%iModNum == 0) checks if the number is divisible (it would return true for iValue = 6 and iModNum = 2, and would therefore say 6 was prime - which it most definitely isn't!)
Here's what I think you meant to so:
bool IsPrime(int iValue){ for(int i = 2; i < iValue; ++i) { if(iValue % i == 0) return false; } // if we got here then none of the numbers divided iValue perfectly return true;} EDIT:
Of course, this method is inefficient in very large iterations. A much better method for determining all prime numbers up to an arbitrarily large limit is to use the Sieve of Eratosthenes and bitsets.
Edited by - Oluseyi on November 1, 2001 2:12:24 PM
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
