C#中的质因数分解

Question

我想创建一个C# 2005程序来计算给定输入的质因数。我想使用基本且最简单的方法，不需要为此创建方法或数组等内容，只需使用简单的模数即可。是否有代码可以满足我的要求？

以下是用于查找简单因子的代码，我需要修改此代码以计算质因数。

class Program
{
    static void Main(string[] args)
    {
        int a, b;
        Console.WriteLine("Please enter your integer: ");
        a = int.Parse(Console.ReadLine());
        for (b = 1; b <= a; b++)
        {
            if (a % b == 0)
            {
                Console.WriteLine(b + " is a factor of " + a);
            }
        }
        Console.ReadLine();



    }
}

- Aliza

---

您应该很容易地自己编写。您卡在哪里了——需要什么帮助？ - Rup

你能否发一些你尝试过的代码吗？你目前有什么代码？ - BZink

这个问题这里有一个很好的算法概述。 - Matt

显示25而不是2和5-你只是使用Console.Write(factor);吗？你可能想在数字之间写一个空格Console.Write(' ');，或者使用Console.WriteLine，或其他方法。 - Rup

这是作业吗，顺便问一下？ - Vilx-

Answer 1

int a, b;
Console.WriteLine("Please enter your integer: ");
a = int.Parse(Console.ReadLine());

for (b = 2; a > 1; b++)
    if (a % b == 0)
    {
        int x = 0;
        while (a % b == 0)
        {
            a /= b;
            x++;
        }
        Console.WriteLine($"{b} is a prime factor {x} times!");
    }
Console.WriteLine("Th-Th-Th-Th-Th-... That's all, folks!");

- Vilx-

---

你需要告诉我们错误在哪里。（顺便说一下，这将消除重复的因素，而不是将其过滤为质数 - 你可能还想显示何时重复了一个质因数？）实际上，你的代码显示1是一个因子 - 错误是它被卡在了无限循环中试图分解1吗？1永远不会是质因数，所以从2开始循环可能更容易，但你确实需要进行质数过滤。 - Rup

给我的机器上运行的徽章作品超级点赞，我要拿走这个。 - Chris Marisic

@Chris Marisic - 这是一件永不过时的“老古董”。 :) - Vilx-

@ChrisMarisic 给他的帖子点个赞并留下你的评论。太聪明了！ - gilles emmanuel

@Charles 很有可能。这段代码并不是很优化，但它简单且能完成任务。 - Vilx-

Answer 2

public static List<int> Generate(int number)
{
    var primes = new List<int>();

    for (int div = 2; div <= number; div++)
        while (number % div == 0)
        {
            primes.Add(div);
            number = number / div;
        }
    
    return primes;
}

如果您想学习开发步骤，您可以在此观看视频。

- Bayram Üçüncü

---

除数永远不能大于数字的一半，因此你可以通过编写以下代码进行优化：for(int div = 2; div<=number / 2; div++){ - stevieg

Answer 3

您可以进一步优化，因为除数永远不会比这个数的平方根更大。

 for(int div = 2; div <= Math.Sqrt(number); div++)

- John Conacher

---

但是在 for 循环结束后，您必须将 number 添加到 primes 列表中... if (number > 1) primes.Add(number); - Cyrus

Answer 4

尝试这段代码（我在这个代码中合并了各种解决方案）。虽然，插值不在2005年（我想是这样的...）

所以，无论如何，请尝试这个：

// C# Program to print all prime factors 
using System; 

namespace prime
{
    public class Prime
    { 

        public static void PrimeFactors(int n)
        {
            Console.Write($"Prime Factors of {n} are:  ");

            // Prints all the numbers of 2  
            while (n % 2 == 0)
            {
                Console.Write("2 ");
                n /= 2;
            }

            // As no 2 can be further divided, this probably means that n
            // is now an odd number
            for(int i = 3; i <= Math.Sqrt(n); i += 2)
            {
                while (n % i == 0)
                {
                    Console.Write($"{i} ");
                    n /= i;
                }
            }

            // This is for case if n is greater than 2
            if (n > 2)
            {
                Console.Write($"{n} ");
            }

        }

        // Prompts user to give Input to number and passes it on 
        // the PrimeFactors function after checking its format
        public static void RunPrimeFactors()
        {
            Console.Write("Enter a number: ");
            if (int.TryParse(Console.ReadLine(), out int n))
            {
                PrimeFactors(n);
            }
            else
            {
                Console.WriteLine("You entered the wrong format");
            }

        }
        // Driver Code 
        public static void Main()
        {
            RunPrimeFactors();
        }

    }
}

- Koroshiya

---

这个解决方案的性能还不错，在大多数情况下比EnumeratePrimeFactors稍微慢一点。 - Charles

Answer 5

最高效的方法是使用优化实现的轮筛法。这里有一个示例，演示了一个只需要考虑形如(30k ± {1, 7, 11, 13})的因子的2, 3, 5轮筛。

public static IEnumerable<T> EnumeratePrimeFactors<T>(this T value) where T : IBinaryInteger<T>, IUnsignedNumber<T> {
    if (BinaryIntegerConstants<T>.Four > value) { yield break; }
    if (BinaryIntegerConstants<T>.Five == value) { yield break; }
    if (BinaryIntegerConstants<T>.Seven == value) { yield break; }
    if (BinaryIntegerConstants<T>.Eleven == value) { yield break; }
    if (BinaryIntegerConstants<T>.Thirteen == value) { yield break; }

    var index = value;

    while (T.Zero == (index & T.One)/* enumerate factors of 2 */) {
        yield return BinaryIntegerConstants<T>.Two;

        index >>= 1;
    }
    while (T.Zero == (index % BinaryIntegerConstants<T>.Three)) { // enumerate factors of 3
        yield return BinaryIntegerConstants<T>.Three;

        index /= BinaryIntegerConstants<T>.Three;
    }
    while (T.Zero == (index % BinaryIntegerConstants<T>.Five)/* enumerate factors of 5 */) {
        yield return BinaryIntegerConstants<T>.Five;

        index /= BinaryIntegerConstants<T>.Five;
    }
    while (T.Zero == (index % BinaryIntegerConstants<T>.Seven)/* enumerate factors of 7 */) {
        yield return BinaryIntegerConstants<T>.Seven;

        index /= BinaryIntegerConstants<T>.Seven;
    }
    while (T.Zero == (index % BinaryIntegerConstants<T>.Eleven)/* enumerate factors of 11 */) {
        yield return BinaryIntegerConstants<T>.Eleven;

        index /= BinaryIntegerConstants<T>.Eleven;
    }
    while (T.Zero == (index % BinaryIntegerConstants<T>.Thirteen)/* enumerate factors of 13 */) {
        yield return BinaryIntegerConstants<T>.Thirteen;

        index /= BinaryIntegerConstants<T>.Thirteen;
    }

    var factor = BinaryIntegerConstants<T>.Seventeen;
    var limit = index.SquareRoot();

    if (factor <= limit) {
        do {
            while (T.Zero == (index % factor)/* enumerate factors of (30k - 13) */) {
                yield return factor;

                index /= factor;
            }

            factor += BinaryIntegerConstants<T>.Two;

            while (T.Zero == (index % factor)/* enumerate factors of (30k - 11) */) {
                yield return factor;

                index /= factor;
            }

            factor += BinaryIntegerConstants<T>.Four;

            while (T.Zero == (index % factor)/* enumerate factors of (30k - 7) */) {
                yield return factor;

                index /= factor;
            }

            factor += BinaryIntegerConstants<T>.Six;

            while (T.Zero == (index % factor)/* enumerate factors of (30k - 1) */) {
                yield return factor;

                index /= factor;
            }

            factor += BinaryIntegerConstants<T>.Two;

            while (T.Zero == (index % factor)/* enumerate factors of (30k + 1) */) {
                yield return factor;

                index /= factor;
            }

            factor += BinaryIntegerConstants<T>.Six;

            while (T.Zero == (index % factor)/* enumerate factors of (30k + 7) */) {
                yield return factor;

                index /= factor;
            }

            factor += BinaryIntegerConstants<T>.Four;

            while (T.Zero == (index % factor)/* enumerate factors of (30k + 11) */) {
                yield return factor;

                index /= factor;
            }

            factor += BinaryIntegerConstants<T>.Two;

            while (T.Zero == (index % factor)/* enumerate factors of (30k + 13) */) {
                yield return factor;

                index /= factor;
            }

            factor += BinaryIntegerConstants<T>.Four;
            limit = index.SquareRoot();
        } while (factor <= limit);
    }

    if ((index != T.One) && (index != value)) {
        yield return index;
    }
}

- Kittoes0124

---

这通常是最快的解决方案，但它使用了yield，我们可能不想要yield。 它使用了在某些地方可能不可用的C# 7特性。 如果一个数本身是素数，则不返回该数字。 - Charles

Answer 6

此版本将所有因子列为显式公式：

static void Main(string[] args)
    {
        Console.WriteLine("Please enter your integer (0 to stop): ");

        int a = int.Parse(Console.ReadLine());
        while(a>0)
        {
            List<int> primeFactors = PrimeFactors(a);
            LogFactorList(primeFactors);
            a = int.Parse(Console.ReadLine());
        }
        Console.WriteLine("Goodbye.");
    }


    /// <summary>
    /// Find prime factors
    /// </summary>
    public static List<int> PrimeFactors(int a)
    {
        List<int> retval = new List<int>();
        for (int b = 2; a > 1; b++)
        {               
            while (a % b == 0)
            {
                a /= b;
                retval.Add(b);
            }               
        }
        return retval;
    }

    /// <summary>
    /// Output factor list to console
    /// </summary>
    private static void LogFactorList(List<int> factors)
    {
        if (factors.Count == 1)
        {
            Console.WriteLine("{0} is Prime", factors[0]);
        }
        else
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < factors.Count; ++i)
            {
                if (i > 0)
                {
                    sb.Append('*');
                }
                sb.AppendFormat("{0}", factors[i]);
            }
            Console.WriteLine(sb.ToString());
        }
    }

- Valid

Answer 7

using static System.Console;

namespace CodeX
{
    public class Program
    {
        public static void Main(string[] args)
        {
            for (int i = 0; i < 20; i++)
            {
                if (IsPrime(i))
                {
                    Write($"{i} ");
                }
            }
        }

        private static bool IsPrime(int number)
        {
            if (number <= 1) return false;  // prime numbers are greater than 1

            for (int i = 2; i < number; i++)
            {
                // only if is not a product of two natural numbers
                if (number % i == 0)       
                    return false;
            }

            return true;
        }
    }
}

- Vincent Amoako-Ampofo

---

请考虑在提供解决问题所需的代码之外，解释您的答案。 - codewario

在维基百科上发现了关于质数的定义。质数从2开始，然后IsPrime(number)方法循环遍历所有从2开始但小于给定数字的数字，以检查是否存在可整除给定数字而不产生余数的数字。 - Vincent Amoako-Ampofo

这段代码并没有回答问题。它打印出了从0到19的所有质数，而不是一个数字的质因数。此外，它非常低效。 - Bip901