check to see if a user entered number is relatively prime 1

[Guest_imported]

Hi, how can I check to see if a user entered number is relatively prime?

Any help appreciated.

 

[snuv]

Try

bool isPrime(long lnPassed)
{
double nRoot = sqrt(lnPassed);
for (long i = 2; i <= nRoot; i++)
{
if (lnPassed%i == 0)
{
return false;
}
}
return true;
}

 

[apkohn]

The above method can be quite slow for large numbers.

Another method would be to run the above function once for all numbers up to some large value, and save the prime values into a file. Then in your program, store the values into an array, and then only try the mod function (%) where i is a prime. Will be quicker at runtime, but memory usage will be higher.

eg

bool IsPrime(long lngNumber)
{
double dblUpperBound = sqrt(lngNumber);

//the following line is pseudocode-esque.
//Populate the array however you want
long KnownPrimes[] = 2,3,7,11 etc...;

int i = 0;

while((KnownPrimes<=dblUpperBound) && (i < SizeOfKnownPrimesArray))
{
if(lngNumber % KnownPrimes == 0)
return False;
i++
}
return true;
}