最优雅的方式来生成素数

Question

实现此功能的最佳方式是什么:

ArrayList generatePrimes(int n)

此函数生成第一个n素数(编辑:where n>1),因此generatePrimes(5)将返回ArrayListwith {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)
• Eratosthenes(星蓝)筛的非常干净的实施
• 使用Java BigInteger和nextProbablePrime非常简单的代码,虽然我无法想象它特别有效(dfa)
• 使用LINQ懒惰地生成素数列表(Maghis)
• 将大量素数放入文本文件中并在必要时读取(darin)

编辑2:我在C#中实现了这里给出的几种方法,以及这里没有提到的另一种方法.他们都有效地找到了前n个素数(我有一个很好的方法来找到提供给筛子的极限).

Answer 1

使用估算值

pi(n) = n / log(n)

对于最多n个素数的数量,找到一个限制,然后使用筛子.估计低估了n的素数,因此筛子将略大于必要的,这是可以的.

这是我的标准Java筛选器,在普通笔记本电脑上计算出大约一秒钟的第一百万个素数:

public static BitSet computePrimes(int limit)
{
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++)
    {
        if (primes.get(i))
        {
            for (int j = i * i; j < limit; j += i)
            {
                primes.clear(j);
            }
        }
    }
    return primes;
}

Answer 2

非常感谢所有给出有益答案的人.以下是我在C#中查找前n个素数的几种不同方法的实现.前两种方法几乎就是这里发布的内容.(海报名称在标题旁边.)我计划在某个时候对阿特金进行筛选,尽管我怀疑它不会像现在的方法那么简单.如果有人能够看到任何改进这些方法的方法我都很想知道:-)

标准方法(彼得·斯密特,jmservera,Rekreativc)

第一个素数是2.将其添加到素数列表中.下一个素数是下一个数字,该数字不能被此列表中的任何数字整除.

public static List<int> GeneratePrimesNaive(int n)
{
    List<int> primes = new List<int>();
    primes.Add(2);
    int nextPrime = 3;
    while (primes.Count < n)
    {
        int sqrt = (int)Math.Sqrt(nextPrime);
        bool isPrime = true;
        for (int i = 0; (int)primes[i] <= sqrt; i++)
        {
            if (nextPrime % primes[i] == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes.Add(nextPrime);
        }
        nextPrime += 2;
    }
    return primes;
}

通过仅测试可测试数字的平方根的可分性来优化这一点; 并且只测试奇数.这可以通过测试形式的只有数字来进一步优化6k+[1, 5],或30k+[1, 7, 11, 13, 17, 19, 23, 29]或等等.

Eratosthenes筛(星蓝)

这找到k的所有素数.为了列出前n个素数,我们首先需要近似第n个素数的值.如此处所述,以下方法可以做到这一点.

public static int ApproximateNthPrime(int nn)
{
    double n = (double)nn;
    double p;
    if (nn >= 7022)
    {
        p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
    }
    else if (nn >= 6)
    {
        p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
    }
    else if (nn > 0)
    {
        p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
    }
    else
    {
        p = 0;
    }
    return (int)p;
}

// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
    BitArray bits = new BitArray(limit + 1, true);
    bits[0] = false;
    bits[1] = false;
    for (int i = 0; i * i <= limit; i++)
    {
        if (bits[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                bits[j] = false;
            }
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfEratosthenes(limit);
    List<int> primes = new List<int>();
    for (int i = 0, found = 0; i < limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(i);
            found++;
        }
    }
    return primes;
}

筛选Sundaram

我最近才发现这个筛子,但它可以很简单地实现.我的实施并不像Eratosthenes的筛子快,但它比天真的方法快得多.

public static BitArray SieveOfSundaram(int limit)
{
    limit /= 2;
    BitArray bits = new BitArray(limit + 1, true);
    for (int i = 1; 3 * i + 1 < limit; i++)
    {
        for (int j = 1; i + j + 2 * i * j <= limit; j++)
        {
            bits[i + j + 2 * i * j] = false;
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfSundaram(limit);
    List<int> primes = new List<int>();
    primes.Add(2);
    for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(2 * i + 1);
            found++;
        }
    }
    return primes;
}

Answer 3

重新解决一个老问题,但我在玩LINQ时偶然发现了它.

此代码需要带有并行扩展的.NET4.0或.NET3.5

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(2, (int)Math.Sqrt(i)).All(j => i % j != 0)
            select i;
    return r.ToList();
}

Answer 4

你走的是好路.

一些评论

• primes.Add(3); 使该函数对number = 1不起作用

• 你没有必要用与要测试的数字的平方根相比更大的主数字来测试除法.

建议代码:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();

    if(toGenerate > 0) primes.Add(2);

    int curTest = 3;
    while (primes.Count < toGenerate)
    {

        int sqrt = (int) Math.sqrt(curTest);

        bool isPrime = true;
        for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
        {
            if (curTest % primes.get(i) == 0)
            {
                isPrime = false;
                break;
            }
        }

        if(isPrime) primes.Add(curTest);

        curTest +=2
    }
    return primes;
}

Answer 5

你应该看看可能的素数.特别是看看随机算法和Miller-Rabin素性测试.

为了完整起见,您可以使用java.math.BigInteger:

public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {

    private BigInteger p = BigInteger.ONE;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public BigInteger next() {
        p = p.nextProbablePrime();
        return p;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return this;
    }
}

@Test
public void printPrimes() {
    for (BigInteger p : new PrimeGenerator()) {
        System.out.println(p);
    }
}

Answer 6

绝不是有效的,但可能最具可读性:

public static IEnumerable<int> GeneratePrimes()
{
   return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
                                     .All(divisor => candidate % divisor != 0));
}

有:

public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
   for (int i = from; i <= to; i++) yield return i;
}

事实上,这里只是一些帖子的变体,格式更好.

Answer 7

2009年版权归St.Wittum 13189 Berlin Berlin根据CC-BY-SA许可 https://creativecommons.org/licenses/by-sa/3.0/

计算所有素数的最简单但最优雅的方法就是这种方法，但是这种方法很慢，并且由于使用了教师功能（！），因此对于较大的数，内存成本要高得多……但是它证明了Wilson Theoreme在通过Python中实现的算法生成所有素数

#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
    if f%p%2:
        print p
    p+=1
    f*=(p-2)