Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * http://csharpcodewhisperer.blogspot.com
- *
- */
- public static class Coprimes
- {
- public static List<uint> FindCoprimes(uint number)
- {
- List<uint> results = new List<uint>();
- if(number<2) {
- return results;
- }
- for (uint count = 2; count < number; count++)
- {
- if(IsCoprime(count,number))
- {
- results.Add(count);
- }
- }
- return results;
- }
- public static bool IsCoprime(uint value1, uint value2)
- {
- return FindGCD(value1, value2) == 1;
- }
- public static uint FindGCDSimple(uint value1, uint value2)
- {
- while(value1 != 0 && value2 != 0)
- {
- if (value1 > value2)
- {
- value1 %= value2;
- }
- else
- {
- value2 %= value1;
- }
- }
- return Math.Max(value1, value2);
- }
- public static uint FindGCDEuclid(uint value1, uint value2)
- {
- while(value1 != 0 && value2 != 0)
- {
- if (value1 > value2)
- {
- value1 -= value2;
- }
- else
- {
- value2 -= value1;
- }
- }
- return Math.Max(value1, value2);
- }
- public static uint FindGCDStein(uint value1, uint value2)
- {
- if (value1 == 0) return value2;
- if (value2 == 0) return value1;
- if (value1 == value2) return value1;
- bool value1IsEven = (value1 & 1u) == 0;
- bool value2IsEven = (value2 & 1u) == 0;
- if (value1IsEven && value2IsEven)
- {
- return FindGCDStein(value1 >> 1, value2 >> 1) << 1;
- }
- else if (value1IsEven && !value2IsEven)
- {
- return FindGCDStein(value1 >> 1, value2);
- }
- else if (value2IsEven)
- {
- return FindGCDStein(value1, value2 >> 1);
- }
- else if (value1 > value2)
- {
- return FindGCDStein((value1 - value2) >> 1, value2);
- }
- else
- {
- return FindGCDStein(value1, (value2 - value1) >> 1);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement