omegasyphon 100 Report post Posted November 1, 2001 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 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted November 1, 2001 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. 0 Share this post Link to post Share on other sites

omegasyphon 100 Report post Posted November 1, 2001 so if i have like 7do i do a loop that does the following7%1 7%2 7%3 7%4 7%5 7%6 7%7and check if its remainder is 0? 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted November 1, 2001 quote:Original post by omegasyphon so if i have like 7do i do a loop that does the following7%1 7%2 7%3 7%4 7%5 7%6 7%7and 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. 0 Share this post Link to post Share on other sites

capn_midnight 1707 Report post Posted November 1, 2001 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 retardsSpyder''s Web Games 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted November 1, 2001 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. 0 Share this post Link to post Share on other sites

omegasyphon 100 Report post Posted November 1, 2001 i think i have itsuppose my number is 7now would i goif 7&x != 0increment x? 0 Share this post Link to post Share on other sites

Mayrel 348 Report post Posted November 1, 2001 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 0 Share this post Link to post Share on other sites

BeerNutts 4401 Report post Posted November 1, 2001 Fellas, the guy just wants a simple function to check if it's prime or not.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.NuttsEdited by - BeerNutts on November 1, 2001 2:01:33 PM 0 Share this post Link to post Share on other sites

Oluseyi 2116 Report post Posted November 1, 2001 'Nutts, I think that function has a bug. The lineif(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 0 Share this post Link to post Share on other sites

Mayrel 348 Report post Posted November 1, 2001 Fast prime number checker.BeerNutts, your function's logic is the wrong way round: it'll return TRUE if a number is not prime, and FALSE otherwise. bool sieve[65536];long primes[65536], primeCount = 0;void initSieve (){ for (int i = 2; i < 65536; ++i) if (!sieve[i]) for (int j = i * 2; j < 65536; j += i) sieve[i] = true; for (int i = 2; i < 65536; ++i) if (!sieve[i]) primes[primeCount++] = i;}bool isPrime (long n){ // If n fits in the sieve, then it's a simple lookup. if (n < 65536) return !sieve[n]; // Elsewise, test it against each prime that is less than sqrt(n) for (int i = 0; (i < primeCount) && (primes[i] < sqrt(n)); ++i) if (0 == n % primes[i]) return false; return true;} Signatures? We don't need no steenking signatures!Edit: Failed to use the English language.Edit: Removed a rogue 7.Edited by - Mayrel on November 1, 2001 2:27:02 PM 0 Share this post Link to post Share on other sites

Guest Anonymous Poster Report post Posted November 1, 2001 There goes the homework assignment... 0 Share this post Link to post Share on other sites

omegasyphon 100 Report post Posted November 1, 2001 thanks, i got it working. 0 Share this post Link to post Share on other sites

BeerNutts 4401 Report post Posted November 1, 2001 Aww, TRUE, FALSE, what's the big difference? Just change those two and it worksOh, and Oluseyi, you're way goes against my coding standards: Only 1 return per function (I know, I'm strict).Edited by - BeerNutts on November 1, 2001 4:35:04 PM 0 Share this post Link to post Share on other sites

Anthracks 122 Report post Posted November 1, 2001 Heh you can tell it''s toward the beginnig of the school year, all these questions cropping up about finding primes, taking the negative of a number without using the - sign, etc .Anthracks 0 Share this post Link to post Share on other sites

Oluseyi 2116 Report post Posted November 2, 2001 quote:Original post by BeerNutts Oh, and Oluseyi, you''re way goes against my coding standards: Only 1 return per function (I know, I''m strict). Interesting paradigm; I use returns to exit early. Besides, some functions do have multiple return values and decaring an extra variable just to hold them isn''t always elegant (boolean functions - as above - come to mind). In any case, to each his own. 0 Share this post Link to post Share on other sites

Mayrel 348 Report post Posted November 2, 2001 quote:Original post by BeerNutts Aww, TRUE, FALSE, what's the big difference? Just change those two and it works In this case, the difference between the A and D grades. quote: Oh, and Oluseyi, you're way goes against my coding standards: Only 1 return per function (I know, I'm strict). You sound like a vulcan, but I don't see no points on your ears, boy.Seriously, you a Pascal programmar in a previous life? Signatures? We don't need no steenking signatures!Edited by - Mayrel on November 2, 2001 9:02:24 AM 0 Share this post Link to post Share on other sites