Here is a little prime tool box I wrote to handle prime numbers, prime factors and divisors. There are a lot of sieves on the interweb, here’s mine.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
public class PrimeToolBox { //internal list of prime numbers private List<int> thePrimeList; //set as read only public IReadOnlyList<int> ThePrimeList { get { return thePrimeList; } } /// <summary> /// Prime toolbox object w/ a list of primes from 2 - primesTo /// </summary> /// <param name="primeTo">Calculate list of primes to this number</param> public PrimeToolBox(int primesTo) { ChangePrimeList(primesTo); } /// <summary> /// Change the size of the internal list of primes /// </summary> /// <param name="primesTo">Updates the prime list from 2 - this number</param> public void ChangePrimeList(int primesTo) { thePrimeList = new List<int>(); thePrimeList.Add(2); int limit = (primesTo - 3) / 2; bool[] sieve = new bool[limit]; //inits as false, for simplicity keep and treat as inverse for (int i = 0; i < limit; i++) { if (sieve[i] == true)//flipped { continue; } thePrimeList.Add(2 * i + 3); for (int j = ((2 * i + 6) * i + 3); j < limit; j += (2 * i + 3)) { sieve[j] = true;//flipped } } } /// <summary> /// Returns a list of a numbers Prime Factors /// </summary> /// <param name="number">to factor</param> /// <returns></returns> public List<int> GetPrimeFactors(int number) { List<int> tempFactors = new List<int>(); foreach (int denominator in this.ThePrimeList.Where(i => i < (number / 2))) { while (number % denominator == 0) { tempFactors.Add(denominator); number = (number / denominator); } } //was it a prime? If so return its value if (number > 1) { tempFactors.Add(number); } return tempFactors; } /// <summary> /// Returns a numbers total divisors. Make sure the Prime list is large enough /// </summary> /// <param name="number"></param> /// <returns></returns> public int GetTotalDivisors(int number) { int totalDivisors = 1; int currentExponent = 1; foreach (int denominator in this.ThePrimeList.Where(i => i < number)) { while (number % denominator == 0) { number = number / denominator; currentExponent += 1; } totalDivisors *= currentExponent; currentExponent = 1; } if (number > 1) { totalDivisors *= 2; } return totalDivisors; } } |
Hope this was helpful.
-John