logo标签列表

生成质数的最优雅方法

c#javaalgorithmprimes
90

如何最优雅地实现这个函数：

ArrayList generatePrimes(int n)

这个函数生成前{{n}}个质数（编辑：其中{{n>1}}），所以generatePrimes(5)将返回一个ArrayList，其中包含{2, 3, 5, 7, 11}。（我是用C#来实现的，但我也可以接受Java - 或者其他类似的语言（不包括Haskell）的实现）。我知道如何编写此函数，但昨晚我写的结果并不如我希望的那么好。以下是我的代码：
ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime += 2;
            }
        }
        primes.Add(nextPrime);
    }
    return primes;
}

我对速度不是太关心，尽管我不希望它明显低效。我不介意使用哪种方法（朴素的还是筛法的还是其他什么的），但我希望它相当简短，并且很明显它是如何工作的。

编辑：感谢所有回复我的人，尽管许多人没有回答我的实际问题。再次强调，我想要一个好的、干净的代码片段来生成质数列表。我已经知道了很多不同的方法，但我往往编写的代码并不像它本应该那样清晰易懂。在这个主题中，有几个好的选择被提出：

  • 一个更好的版本，与我最初拥有的相似（Peter Smit、jmservera和Rekreativc）
  • 一个非常干净的埃拉托色尼筛法实现（starblue）
  • 使用Java的BigInteger和nextProbablePrime来编写非常简单的代码，尽管我无法想象它特别高效（dfa）
  • 使用LINQ来懒惰地生成质数列表（Maghis）
  • 在文本文件中放置大量质数，并在必要时读取它们（darin）

编辑 2: 我已经在 C# 中实现了这里给出的一些方法，还有另一种方法没有在这里提到。它们都可以有效地找到前n个质数（我有一个不错的方法来找到提供给筛子的限制）。

1
最好返回一个IEnumerable<int>并逐个yield。 - Felice Pollano
4
我想知道生成质数的最不优雅的方式是什么。我在考虑是否涉及使用Access数据库？ - j_random_hacker
1
对比一下，这是BMeph在2008年写的Haskell代码：nubBy (((>1).).gcd) [2..]。它只保留自然数中从2开始的非重复数字，同时将任何与先前找到的数字之一的gcd大于1的数字视为重复。它非常低效，产生的质数数量平方级增长。但它很优雅。 - Will Ness
在我看来，最优雅的语言是Haskell，它的代码如下：import Data.List.Ordered ; let { _Y g = g (_Y g) ; primes = 2 : _Y( (3:) . minus [5,7..] . unionAll . map (\p-> [p*p, p*p+p*2..]) ) } 当然，这完全基于个人观点。 - Will Ness
你要寻找什么类型的质数？它们需要通过哪些测试？ - jww
25个回答
3
使用相同的算法，您可以更简洁地完成它：
List<int> primes=new List<int>(new int[]{2,3});
for (int n = 5; primes.Count< numberToGenerate; n+=2)
{
  bool isPrime = true;
  foreach (int prime in primes)
  {
    if (n % prime == 0)
    {
      isPrime = false;
      break;
    }
  }
  if (isPrime)
    primes.Add(n);
}
3

我知道你要求非Haskell的解决方案，但是我还是包括在这里，因为它与问题有关，而且Haskell对于这种类型的事情非常美妙。

module Prime where

primes :: [Integer]
primes = 2:3:primes'
  where
    -- Every prime number other than 2 and 3 must be of the form 6k + 1 or 
    -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
    -- prime (6*0+5 == 5) to start the recursion.
    1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n      = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p    = n `mod` p == 0
是的，我也是 Haskell 的粉丝（只是希望我更了解它）。 - David Johnstone
3

我使用了一些LINQ在c#中编写了一个简单的埃拉托色尼筛法实现。

不幸的是，LINQ没有提供无限的int序列，所以你必须使用int.MaxValue:(

为了避免为每个缓存的素数计算它，我不得不在匿名类型中缓存候选平方根（看起来有点丑）。

我使用了一个先前素数列表，直到候选数的平方根。

cache.TakeWhile(c => c <= candidate.Sqrt)

并检查从2开始的每个整数是否与它相等

.Any(cachedPrime => candidate.Current % cachedPrime == 0)

以下是代码：

static IEnumerable<int> Primes(int count)
{
    return Primes().Take(count);
}

static IEnumerable<int> Primes()
{
    List<int> cache = new List<int>();

    var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new 
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}

另一个优化方法是避免检查偶数，并在创建列表之前仅返回2。这样，如果调用方法只请求1个质数，它将避免所有混乱。
static IEnumerable<int> Primes()
{
    yield return 2;
    List<int> cache = new List<int>() { 2 };

    var primes = Enumerable.Range(3, int.MaxValue - 3)
        .Where(candidate => candidate % 2 != 0)
        .Select(candidate => new
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}
1
我希望我足够了解LINQ，以便更好地欣赏和理解这个答案 :-) 另外，我有一种感觉，这不是Eratosthenes筛法的实现，它在概念上与我的原始函数相同（查找下一个不能被先前发现的任何质数整除的数字）。 - David Johnstone
是的，但“找到下一个不能被先前找到的质数（小于该数字）整除的数字”在概念上类似于厄拉多塞筛法。如果您愿意，我可以进行重构，使其更易于阅读，即使您不熟悉LINQ也可做到。您是否熟悉迭代器？ - Maghis
我喜欢这种方法的原因是，下一个质数只有在调用者要求时才计算，因此像“取前n个质数”或“取小于n的质数”之类的事情变得微不足道。 - Maghis
1
谢谢，但我足够理解它的作用了 :-) 我喜欢惰性求值，但我仍然不会称其为埃拉托斯特尼筛法的实现。 - David Johnstone
1

试一下这个LINQ查询，它会按照你的预期生成素数

        var NoOfPrimes= 5;
        var GeneratedPrime = Enumerable.Range(1, int.MaxValue)
          .Where(x =>
            {
                 return (x==1)? false:
                        !Enumerable.Range(1, (int)Math.Sqrt(x))
                        .Any(z => (x % z == 0 && x != z && z != 1));
            }).Select(no => no).TakeWhile((val, idx) => idx <= NoOfPrimes-1).ToList();
1

这是我能在短时间内想到的最优雅的方式。

ArrayList generatePrimes(int numberToGenerate)
{
    ArrayList rez = new ArrayList();

    rez.Add(2);
    rez.Add(3);

    for(int i = 5; rez.Count <= numberToGenerate; i+=2)
    {
        bool prime = true;
        for (int j = 2; j < Math.Sqrt(i); j++)
        {
            if (i % j == 0)
            {
                    prime = false;
                    break;
            }
        }
        if (prime) rez.Add(i);
    }

    return rez;
}

希望这能给你一个思路。我相信这可以进行优化，但它应该能让你了解如何使你的版本更加优雅。
编辑：正如评论中所指出的，对于numberToGenerate < 2，此算法确实返回错误的值。我只是想指出，我并不打算给他提供一个生成素数的好方法（请看亨利的答案），我只是想指出他的方法如何更加优雅。
3
当 numberToGenerate < 2 时，这个函数返回了错误的结果。 - Peter Smit
这是正确的，但我并没有设计算法，我只是向他展示了如何使他的方法更加优雅。因此，这个版本和开头问题中的那个一样错误。 - David Božjak
1
我没想到n=1时会出问题。我稍微改了一下问题，让函数只需要在n>1的情况下工作 :-) - David Johnstone
这个程序将平方数素数识别为素数。 - Will Ness
1

我用Java编写了一个函数库来实现它，但由于我的库使用与枚举相同的概念，所以我确信代码是可适应的：

Iterable<Integer> numbers = new Range(1, 100);
Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>()
{
    public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception
    {
        // We don't test for 1 which is implicit
        if ( number <= 1 )
        {
            return numbers;
        }
        // Only keep in numbers those that do not divide by number
        return numbers.reject(new Functions.Predicate1<Integer>()
        {
            public Boolean call(Integer n) throws Exception
            {
                return n > number && n % number == 0;
            }
        });
    }
});
1

在Functional Java中使用基于流的编程，我得出了以下结论。类型Natural本质上是BigInteger >= 0。

public static Stream<Natural> sieve(final Stream<Natural> xs)
{ return cons(xs.head(), new P1<Stream<Natural>>()
  { public Stream<Natural> _1()
    { return sieve(xs.tail()._1()
                   .filter($(naturalOrd.equal().eq(ZERO))
                           .o(mod.f(xs.head())))); }}); }

public static final Stream<Natural> primes
  = sieve(forever(naturalEnumerator, natural(2).some()));

现在你有一个值，可以带着走，那就是一个无限的素数流。你可以做如下操作：
// Take the first n primes
Stream<Natural> nprimes = primes.take(n);

// Get the millionth prime
Natural mprime = primes.index(1000000);

// Get all primes less than n
Stream<Natural> pltn = primes.takeWhile(naturalOrd.lessThan(n));

筛法的解释：

  1. 假设参数流中的第一个数字是质数，并将其放在返回流的前面。只有在被要求时才会产生返回流的其余计算。
  2. 如果有人要求流的其余部分，请对参数流的其余部分调用筛选器，过滤掉可被第一个数字整除的数字（除法的余数为零）。

您需要导入以下内容：

import fj.P1;
import static fj.FW.$;
import static fj.data.Enumerator.naturalEnumerator;
import fj.data.Natural;
import static fj.data.Natural.*;
import fj.data.Stream;
import static fj.data.Stream.*;
import static fj.pre.Ord.naturalOrd;
1

我个人认为这是一个相当简洁清晰的（Java）实现：

static ArrayList<Integer> getPrimes(int numPrimes) {
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    int n = 2;
    while (primes.size() < numPrimes) {
        while (!isPrime(n)) { n++; }
        primes.add(n);
        n++;
    }
    return primes;
}

static boolean isPrime(int n) {
    if (n < 2) { return false; }
    if (n == 2) { return true; }
    if (n % 2 == 0) { return false; }
    int d = 3;
    while (d * d <= n) {
        if (n % d == 0) { return false; }
        d += 2;
    }
    return true;
}
1
// Create a test range
IEnumerable<int> range = Enumerable.Range(3, 50 - 3);

// Sequential prime number generator
var primes_ = from n in range
     let w = (int)Math.Sqrt(n)
     where Enumerable.Range(2, w).All((i) => n % i > 0)
     select n;

// Note sequence of output:
// 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
foreach (var p in primes_)
    Trace.Write(p + ", ");
Trace.WriteLine("");
1
为了使代码更加优雅，你应该将判断质数的测试重构为一个独立的方法，并在外部处理循环和增量。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接