C#质因数
题目：将一个正整数分解质因数。例如：输入90,打印出90=2*3*3*5。
程序分析：对n进行分解质因数，应先找到一个最小的质数k，然后按
* 下述步骤完成： (1)如果这个质数恰等于n，则说明分解质因数的
* 过程已经结束，打印出即可。 (2)如果n <> k，但n能被k整除，
* 则应打印出k的值，并用n除以k的商,作为新的正整数你n,重复执行
* 第一步.(3)如果n不能被k整除，则用k+1作为k的值,重复执行第一步。
[解决办法]
既然LZ把算法都给出，代码应该好写了。
只是这个算法里有个小问题，(3)里面需要判断新生k是否为质数。以下用一个动态数组跟踪已经遇到的质数，而之后的质数判断只要看是否能被已经遇到的质数整除（判断只要检查到这个被判断数的平方根即可）。另外这个递进可以用+2而不是+1，因为除2以外的质数都是奇数，但2可能是最小递进单位了，因为质数的性质是很乖张的，著名的孪生素数猜想（不知道是不是已经证明了）就是说无论多大都有可能有以2为间隔的质数。另外就算这样这个算法也不知道是不是最优的（其实很好时间，如果输入数是一个大质数就要花很长的时间），优化要靠数论理论，要知道数论有时被称为数学皇冠上的明珠。
using System;using System.Collections.Generic;namespace ConsoleApplication1{ class Program { /// <summary> /// get the prime factors of <paramref name="value"/> /// </summary> /// <param name="value">the value to get prime factors of</param> /// <returns>prime factors stored in a list</returns> static List<uint> GetFactors(uint value) { List<uint> factors = new List<uint>(); // list of factors to return List<uint> primes = new List<uint>(); // prime numbers encountered uint k = 2; // initial prime number primes.Add(k); // load the first prime number to the prime list while (true) { if (value == k) { factors.Add(k); break; } else if (value % k == 0) { factors.Add(k); value /= k; } else { bool isPrime; do { k+=2; isPrime = true; foreach (uint prime in primes) { // k is divisible by 'prime' // k is not a prime number if (k % prime == 0) { isPrime = false; break; } if (prime > Math.Sqrt(k)) { // no need to check other numbers break; } } } while (!isPrime); primes.Add(k); // add k to the list } } return factors; } static void Main(string[] args) { Console.Write("Input a number: "); string input = Console.ReadLine(); uint value = Convert.ToUInt32(input); List<uint> factors = GetFactors(value); Console.Write("{0} = ", value); for (int i = 0; i < factors.Count - 1; i++) { Console.Write("{0} * ", factors[i]); // print the factors except for the last } Console.WriteLine("{0}", factors[factors.Count - 1]); // print the last factor } }}
[解决办法]
static List<int> GetPrimes(int m){ List<int> primes = new List<int>(); for (int i = 2; i <= m; ) { if (IsPrime(i) && m % i == 0) { primes.Add(i); m /= i; } else { i++; } } return primes;}static bool IsPrime(int m){ if (m == 2) return true; if (m == 1 || m % 2 == 0) return false; for (int i = 3; i * i < m; i += 2) { if (m % i == 0) return false; } return true;}
[解决办法]