高效的算法来获得两个大数之间的素数

Question

我是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);
            }
        }
    }

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

Answer 1

我记得像这样解决问题:

1. 使用埃拉托色尼筛产生下面的所有素数sqrt(1000000000) = ~32 000在数组中primes.
2. 对于x之间的每个数字m,n只测试它是否为素数,通过测试<= sqrt(x)数组中数字的可分性primes.因此,x = 29你只会测试它是否可以分辨2, 3 and 5.

有一个在检查对非质数整除是没有意义的,因为如果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]通常在教程和教科书中提供.然而,这可能变得非常难看,并且不需要它.但如果有人有兴趣,请参阅:

http://pastie.org/9199654和这个相关的答案.

Answer 2

你正在做很多不需要的额外划分 - 如果你知道一个数字不能被3整除,那么检查它是否可以被9,27等整除是没有意义的.你应该试图仅仅通过潜力来划分数量的主要因素.缓存您生成的素数集,并仅检查前一个素数的除法.请注意,您确实需要生成低于L1的初始素数集.

请记住,没有数字的主要因子大于其自己的平方根,因此您可以在此时停止分割.例如,您可以在5之后停止检查数字29的潜在因素.

你也可以增加2,所以你可以忽略检查一个偶数是否完全是素数(当然,特殊套管数字2).

我曾经在采访中提出这个问题 - 作为一项测试,我将一个类似于你的实现与我描述的算法进行了比较.使用优化的算法,我可以非常快速地生成数十万个素数 - 我从不费心等待缓慢,直接的实现.