在两个大数之间获取质数的高效算法

  • Z时代
  • 2024-01-10
  • 分类：问答

我是C＃的初学者，我正在尝试编写一个应用程序来获取用户输入的两个数字之间的素数。问题是：在大数（有效数字范围是1到1000000000）中，获取质数会花费很长时间，并且根据我要解决的问题，整个操作必须在较小的时间间隔内进行。这是更多说明的问题链接：

SPOJ-Prime

这是我的代码中负责获取素数的部分：

  public void GetPrime()
    {            
        int L1 = int.Parse(Limits[0]);
        int L2 = int.Parse(Limits[1]);
        if (L1 == 1)
        {
            L1++;
        }
        for (int i = L1; i <= L2; i++)
        {
            for (int k = L1; k <= L2; k++)
            {
                if (i == k)
                {
                    continue;
                }
                else if (i % k == 0)
                {
                    flag = false;
                    break;
                }
                else
                {
                    flag = true;
                }
            }
            if (flag)
            {
                Console.WriteLine(i);
            }
        }
    }

有没有更快的算法？提前致谢。

回答：

我记得解决这样的问题：

  1. 使用埃拉托色尼筛产生下面的所有素数sqrt(1000000000) = ~32 000在数组中primes。

  2. 对于x之间的每个数字m，n仅通过测试<= sqrt(x)与数组中数字的可除性来测试其是否为质数primes。因此，对于x = 29您来说，只会测试它是否可除2, 3 and 5。

检查非素数的可除性是没有意义的，因为if x divisible by non-prime y，则存在p < y诸如这样的素数x

divisible by p，因为我们可以写成y素数的乘积。例如，12是由整除6，但是6 = 2 *

3，这意味着12也整除2或3。通过提前生成所有需要的素数（这种情况下很少），您可以大大减少实际素数测试所需的时间。

这将被接受，并且不需要对筛进行任何优化或修改，这是一个非常干净的实现。

您可以通过将筛子泛化以在一定间隔内生成素数来更快地完成此操作[left, right]，[2,

right]这与教程和教科书中通常介绍的不同。但是，这可能很难看，并且不需要。

以上是 在两个大数之间获取质数的高效算法 的全部内容， 来源链接： utcz.com/qa/402006.html

回到顶部