高效的算法，得到两个大数的质数 [英] Efficient algorithm to get primes between two large numbers

问题描述

我在C＃初学者，我试图写一个应用程序来获取用户输入两个数字之间的素数。现在的问题是：在大数（有效号码的范围是从1〜1000000000）得到素数需要很长的时间，并根据我解决问题，整个操作必须在一个小的时间间隔进行。这就是问题的链接，更多的解释： SPOJ总理

I'm a beginner in C#, I'm trying to write an application to get primes between two numbers entered by the user. The problem is: At large numbers (valid numbers are in the range from 1 to 1000000000) getting the primes takes long time and according to the problem I'm solving, the whole operation must be carried out in a small time interval. This is the problem link for more explanation: SPOJ-Prime

这是我的code中的一部分，这是负责任的越来越素数：

And here's the part of my code that's responsible of getting primes:

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

有没有更快的算法？ 先谢谢了。

Is there any faster algorithm? Thanks in advance.

推荐答案

我记得解决这个问题是这样的：

I remember solving the problem like this:

1. 使用埃拉托色尼的筛以生成以下的sqrt（10亿）的所有素数=〜32 000 在一个数组素数。
2. 对于每个编号之间的 M X 和 N 如果它是主要通过测试整除反对数只考＆LT; =的sqrt（x）从数组素数。因此，对于 X = 29 你会如果它是divisibile通过只考2，3，5 。

1. Use the sieve of eratosthenes to generate all primes below sqrt(1000000000) = ~32 000 in an array primes.
2. For each number x between m and n only test if it's prime by testing for divisibility against numbers <= sqrt(x) from the array primes. So for x = 29 you will only test if it's divisibile by 2, 3 and 5.

有一个在检查可分对非质数没有任何意义，因为如果 X整除非黄金是，则存在一个素点＆LT;是，使得由P X [整除，因为我们可以写是作为产品素数。例如， 12 是 6 整除，但 6 = 2 * 3 ，这意味着 12 也整除 2 或 3 。通过生成所有需要的素数提前（有在这种情况下，非常少），则显著减少所需的实际素性测试的时间。

There's no point in checking for divisibility against non-primes, since if x divisible by non-prime y, then there exists a prime p < y such that x divisible by p, since we can write y as a product of primes. For example, 12 is divisible by 6, but 6 = 2 * 3, which means that 12 is also divisible by 2 or 3. By generating all the needed primes in advance (there are very few in this case), you significantly reduce the time needed for the actual primality testing.

这会得到接受，并且不需要任何的优化或修改筛，这是一个pretty的清洁实施。

This will get accepted and doesn't require any optimization or modification to the sieve, and it's a pretty clean implementation.

您可以更快地做到这一点通过要概括筛产生在区间的质数 [左，右] ，不是 [2，右] 喜欢它通常$ psented的教程，教材p $。这可以得到pretty的丑但是，这是没有必要的。但是，如果有人有兴趣，请参见：

You can do it faster by generalising the sieve to generate primes in an interval [left, right], not [2, right] like it's usually presented in tutorials and textbooks. This can get pretty ugly however, and it's not needed. But if anyone is interested, see:

http://pastie.org/9199654 和<一href="http://stackoverflow.com/questions/19635294/is-a-recursive-iterative-method-better-than-a-purely-iterative-method-to-find-ou/19641049#19641049">this联答案。

这篇关于高效的算法，得到两个大数的质数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！