首页>Program>source

我正在写一些与质数有关的方法的小图书馆.完成基础工作(又称工作方法)后,现在我正在寻找一些优化方法。 当然,互联网是一个理想的选择.但是,我偶然发现了一个舍入问题,我想知道如何解决这个问题。

在循环中,我使用一个数字来测试其素数,搜索直到sqrt(n)而不是n / 2甚至n-1更为有效。但是由于舍入问题,一些数字被跳过,因此一些质数 跳过! 例如,第10000个素数应为:104729,但"优化"版本的结尾为:103811。

一些代码(我知道它可以进行更多优化,但是我一次只能处理一件事)

/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
    // 0 and 1 are not prime numbers
    if (test == 0 || test == 1) return false;
    // 2 and 3 are prime numbers
    if (test == 2) return true;
    // all even numbers, save 2, are not prime
    if (test % 2 == 0) return false;
    double squared = Math.Sqrt(test);
    int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));
    // start with 5, make increments of 2, even numbers do not need to be tested
    for (int idx = 3; idx < flooredAndSquared; idx++)
    {
        if (test % idx == 0)
        {
            return false;
        }
    }
    return true;
}

我知道平方的部分使我失败(或失败),也尝试过Math.Ceiling,结果大致相同。

最新回答
  • 11天前
    1 #

    遗憾的是,我之前没有尝试过算法方法.但是,如果您想有效地实现您的方法,建议您进行一些缓存.创建一个数组来存储所有小于定义阈值的素数,填充该数组,然后在其中/使用它进行搜索。

    在下面的示例中,在最佳情况下(即,当该数字小于或等于 maxPrime时),查找数字是否为质数为O(1)。 ,对于64K缓冲区,它为821,461),并针对其他情况进行了一些优化(通过检查前820,000个中的仅64K数字是否为mod -大约为8%)。

    (注意:请勿将此答案视为"最佳"方法。它更多是有关如何优化实现的示例。)

    public static class PrimeChecker
    {
        private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB
        private static int[] primes;
        public static int MaxPrime { get; private set; }
        public static bool IsPrime(int value)
        {
            if (value <= MaxPrime)
            {
                return Array.BinarySearch(primes, value) >= 0;
            }
            else
            {
                return IsPrime(value, primes.Length) && IsLargerPrime(value);
            }
        }
        static PrimeChecker()
        {
            primes = new int[BufferSize];
            primes[0] = 2;
            for (int i = 1, x = 3; i < primes.Length; x += 2)
            {
                if (IsPrime(x, i))
                    primes[i++] = x;
            }
            MaxPrime = primes[primes.Length - 1];
        }
        private static bool IsPrime(int value, int primesLength)
        {
            for (int i = 0; i < primesLength; ++i)
            {
                if (value % primes[i] == 0)
                    return false;
            }
            return true;
        }
        private static bool IsLargerPrime(int value)
        {
            int max = (int)Math.Sqrt(value);
            for (int i = MaxPrime + 2; i <= max; i += 2)
            {
                if (value % i == 0)
                    return false;
            }
            return true;
        }
    }
    

  • 11天前
    2 #

    我想这是您的问题:

    for (int idx = 3; idx < flooredAndSquared; idx++)
    

    应该是

    for (int idx = 3; idx <= flooredAndSquared; idx++)
    

    所以您不会得到平方数作为质数.另外,您可以使用" idx + = 2"代替" idx ++",因为您只需要测试奇数(如您在上面的评论中所写...)。

  • 11天前
    3 #

    我不 知道这是否正是您要寻找的东西,但是如果您真的关心速度,那么应该研究概率性方法来测试素数而不是使用筛子. Rabin-Miller是Mathematica使用的概率素数测试。

  • 11天前
    4 #

    我在这里发布了一个使用筛子或Eratosthenesnes来计算素数的类:

    数组的大小是否受int的上限(2147483647)约束?

  • 11天前
    5 #

    如Mark所说,Miller-Rabin检验实际上是一种非常好的方法.另一个参考(带有伪代码)是有关它的wikipedia文章。

    应该注意,虽然它是概率性的,但是通过仅测试极少数情况,您可以确定数字对于整数(且接近长整数)范围而言是否是质数.有关更多详细信息,请参见该wikipedia文章的这一部分或Primality Proving参考。

    我还建议阅读这篇有关模幂的文章,否则,当您尝试进行Miller-Rabin测试时,您将要处理非常大的数字...

  • knockout.js:KnockoutJS ObservableArray数据分组
  • c#:NET的webBrowser类的异步/等待实现