Archived

This topic is now archived and is closed to further replies.

prime number question

This topic is 5885 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Nutts

Edited by - BeerNutts on November 1, 2001 2:01:33 PM

Share this post


Link to post
Share on other sites
'Nutts, I think that function has a bug. The line
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Aww, TRUE, FALSE, what's the big difference? Just change those two and it works

Oh, 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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites