日期:2014-05-18  浏览次数:20836 次

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为间隔的质数。另外就算这样这个算法也不知道是不是最优的(其实很好时间,如果输入数是一个大质数就要花很长的时间),优化要靠数论理论,要知道数论有时被称为数学皇冠上的明珠。


C# code

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
        }
    }
}

------解决方案--------------------
C# code

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