Advertisement
BurningBunny

Find coprimes of integer in C#

Jul 12th, 2013
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.70 KB | None | 0 0
  1. /*
  2.  *  http://csharpcodewhisperer.blogspot.com
  3. *
  4.  */
  5. public static class Coprimes
  6. {
  7.     public static List<uint> FindCoprimes(uint number)
  8.     {
  9.         List<uint> results = new List<uint>();
  10.         if(number<2) {
  11.             return results;
  12.         }
  13.        
  14.         for (uint count = 2; count < number; count++)
  15.         {
  16.             if(IsCoprime(count,number))
  17.             {
  18.                 results.Add(count);
  19.             }
  20.         }
  21.         return results;
  22.     }
  23.    
  24.     public static bool IsCoprime(uint value1, uint value2)
  25.     {
  26.         return FindGCD(value1, value2) == 1;
  27.     }
  28.    
  29.     public static uint FindGCDSimple(uint value1, uint value2)
  30.     {
  31.         while(value1 != 0 && value2 != 0)
  32.         {
  33.             if (value1 > value2)
  34.             {
  35.                 value1 %= value2;
  36.             }
  37.             else
  38.             {
  39.                 value2 %= value1;
  40.             }
  41.         }
  42.         return Math.Max(value1, value2);
  43.     }
  44.  
  45.     public static uint FindGCDEuclid(uint value1, uint value2)
  46.     {
  47.         while(value1 != 0 && value2 != 0)
  48.         {
  49.             if (value1 > value2)
  50.             {
  51.                 value1 -= value2;
  52.             }
  53.             else
  54.             {
  55.                 value2 -= value1;
  56.             }
  57.         }
  58.         return Math.Max(value1, value2);
  59.     }
  60.  
  61.     public static uint FindGCDStein(uint value1, uint value2)
  62.     {
  63.         if (value1 == 0) return value2;
  64.         if (value2 == 0) return value1;
  65.         if (value1 == value2) return value1;
  66.  
  67.         bool value1IsEven = (value1 & 1u) == 0;
  68.         bool value2IsEven = (value2 & 1u) == 0;
  69.                
  70.         if (value1IsEven && value2IsEven)
  71.         {
  72.             return FindGCDStein(value1 >> 1, value2 >> 1) << 1;
  73.         }
  74.         else if (value1IsEven && !value2IsEven)
  75.         {
  76.             return FindGCDStein(value1 >> 1, value2);
  77.         }
  78.         else if (value2IsEven)
  79.         {
  80.             return FindGCDStein(value1, value2 >> 1);
  81.         }
  82.         else if (value1 > value2)
  83.         {
  84.             return FindGCDStein((value1 - value2) >> 1, value2);
  85.         }
  86.         else
  87.         {
  88.             return FindGCDStein(value1, (value2 - value1) >> 1);
  89.         }
  90.     }
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement