I need help figuring out if two numbers are co-prime.

So far I have this (prime() is a bool function)

void GetE(int& e, int& result)
	int random = rand();

			if(random < result)
				e = random;
				random = rand();
			random = rand();
	}while(prime(random) && random < result);


As you can see:
- I have an int result (already found through previous functions)
- I need to generate a random number.
- If that number is prime, and if less than result, I got my number.
- Else, get a new random number.

My goal is to get a random PRIME number that is LESS than result.

I could also use a coprime to result, but am unsure how to code that using the Euclidean Algorithm. I've tried but can't get it to work.

Also, cplusplus.com is down now so I can't use that as a reference, which I need to :(

Thanks in advance for any help.

Edited by MrJNV: n/a

6 Years
Discussion Span
Last Post by arkoenig

That is nearly all Greek to me, sorry.

However, I used the algorithm in a LCM function already (which used GCD), taking two known int's as parameters.

However, I can't figure out how to take the result, and find another random prime LESS than result.


The trouble is that the general technique of picking random numbers and seeing if they're prime is not guaranteed to terminate. For example, if "result" is 2, then there isn't any prime number less than it.

And why does the prime number you pick need to be random? After all, if "result" is greater than 2, then 2 is a prime number that is less than result. What do you hope to gain by this randomness?

Edited by arkoenig: Additional information.

This article has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.