存储质数列表<long>

Question

我正在编写一个计算质因数的程序，我需要下一个质数来查看我的输入数是否可整除。素数列表，直到一个足够大的数，是已知的。 Example.

我的问题是，在我的 C# 代码中存储前 10,000 个质数的列表并在计算质因数时使用它是好还是坏？

Answer 1

您可以改为存储偏移量：

如果你的素数是：2,3,5,7,11,13,17,19,23,29,31,37,41,43

那么你的偏移量将是（base=2）：0, 1, 1, 2, 2, 3, 2, 4, 2, 4, 6, 2, 6, 4, 2, ...

基本上，偏移量只是列表中一个素数和下一个素数之间的差值。从数学上讲，我不确定这是否真的会节省很多 space 但它可能值得研究。您很可能会使用较小的数据类型来覆盖相同的数字 space.

这里有一篇关于 "prime gap" 的有趣读物，它向您展示了在非常大的素数中素数的差异保持相对较小：https://en.wikipedia.org/wiki/Prime_gap

如果您只存储 10,000 个素数，这是毫无意义的。只需存储它们或计算它们。

Answer 2

我要做的是创建一个布尔函数，该函数可以 return 一个布尔值，具体取决于该值是否为 PrimeNumber。

private bool IsPrimeNumber(int value)
{
    for(int i = 2; i < value; i++)
    {
        if(value % i == 0)//If the remainder of "value" divided by "i" is equal to 0.
        {
            return false;
        }
    }
    return true;
}

然后我将创建确定一个值的所有质因数的函数。

private int[] primefactors(int value)
{
    if (value < 0)
    {
        throw new Exception("Value can't be less than 0.");//Make sure value is not less than 0.
    }
    List<int> primefactors = new List<int>();
    for(int i = 2; i < value; i++)
    {
        if (value % i == 0 && IsPrimeNumber(i))//If the remainder of "value" divided by "i" is equal to 0 and "i" is a prime number.
        {
            factors.Add(i);
        }
    }
    return primefactors.ToArray();
}

存储质数列表<long>

Storing a List<long> of Prime Numbers

c#

.net

prime-factoring