生成质数的最优雅方法

Question

生成质数的最优雅方法

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个质数（我有一个不错的方法来找到提供给筛子的限制）。

- David Johnstone

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个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- riz · Answer 1

试试这段代码。

protected bool isPrimeNubmer(int n)
    {
        if (n % 2 == 0)
            return false;
        else
        {
            int j = 3;
            int k = (n + 1) / 2 ;

            while (j <= k)
            {
                if (n % j == 0)
                    return false;
                j = j + 2;
            }
            return true;
        }
    }
    protected void btn_primeNumbers_Click(object sender, EventArgs e)
    {
        string time = "";
        lbl_message.Text = string.Empty;
        int num;

        StringBuilder builder = new StringBuilder();

        builder.Append("<table><tr>");
        if (int.TryParse(tb_number.Text, out num))
        {
            if (num < 0)
                lbl_message.Text = "Please enter a number greater than or equal to 0.";
            else
            {
                int count = 1;
                int number = 0;
                int cols = 11;

                var watch = Stopwatch.StartNew();

                while (count <= num)
                {
                    if (isPrimeNubmer(number))
                    {
                        if (cols > 0)
                        {
                            builder.Append("<td>" + count + " - " + number + "</td>");
                        }
                        else
                        {
                            builder.Append("</tr><tr><td>" + count + " - " + number + "</td>");
                            cols = 11;
                        }
                        count++;
                        number++;
                        cols--;
                    }
                    else
                        number++;
                }
                builder.Append("</table>");
                watch.Stop();
                var elapsedms = watch.ElapsedMilliseconds;
                double seconds = elapsedms / 1000;
                time = seconds.ToString();
                lbl_message.Text = builder.ToString();
                lbl_time.Text = time;
            }
        }
        else
            lbl_message.Text = "Please enter a numberic number.";

        lbl_time.Text = time;

        tb_number.Text = "";
        tb_number.Focus();
    }

这是aspx代码。

<form id="form1" runat="server">
    <div>
        <p>Please enter a number: <asp:TextBox ID="tb_number" runat="server"></asp:TextBox></p>

        <p><asp:Button ID="btn_primeNumbers" runat="server" Text="Show Prime Numbers" OnClick="btn_primeNumbers_Click" />
        </p>
        <p><asp:Label ID="lbl_time" runat="server"></asp:Label></p>
        <p><asp:Label ID="lbl_message" runat="server"></asp:Label></p>
    </div>
</form>

结果：在不到一秒钟内找到10000个质数

在63秒内找到100000个质数

前100个质数的截图输入图像描述

- Nicholas Jordan · Answer 2

我是通过先在维基上阅读“阿特金筛法”以及之前的一些思考得到这个结果的 - 我花了很多时间从头开始编码，完全专注于那些批评我的编译器般、非常密集的编码风格的人 + 我甚至还没有尝试运行代码的第一次尝试...我学习使用的许多范例都在这里，只需阅读并领悟，获取你所需要的。

在任何使用之前，请务必彻底测试所有内容，千万不要向任何人展示 - 这仅供阅读和考虑想法。我需要让素性工具正常工作，所以每次我需要让某些东西正常工作时，我都会从这里开始。

首先进行一次干净的编译，然后开始去除有缺陷的部分 - 我用这种方式几乎打出了1.08亿个可用代码的按键次数，...使用你所能使用的。

我明天会继续开发我的版本。

package demo;
// This code is a discussion of an opinion in a technical forum.
// It's use as a basis for further work is not prohibited.
import java.util.Arrays;
import java.util.HashSet;
import java.util.ArrayList;
import java.security.GeneralSecurityException;

/**
 * May we start by ignores any numbers divisible by two, three, or five
 * and eliminate from algorithm 3, 5, 7, 11, 13, 17, 19 completely - as
 * these may be done by hand. Then, with some thought we can completely
 * prove to certainty that no number larger than square-root the number
 * can possibly be a candidate prime.
 */

public class PrimeGenerator<T>
{
    //
    Integer HOW_MANY;
    HashSet<Integer>hashSet=new HashSet<Integer>();
    static final java.lang.String LINE_SEPARATOR
       =
       new java.lang.String(java.lang.System.getProperty("line.separator"));//
    //
    PrimeGenerator(Integer howMany) throws GeneralSecurityException
    {
        if(howMany.intValue() < 20)
        {
            throw new GeneralSecurityException("I'm insecure.");
        }
        else
        {
            this.HOW_MANY=howMany;
        }
    }
    // Let us then take from the rich literature readily 
    // available on primes and discount
    // time-wasters to the extent possible, utilizing the modulo operator to obtain some
    // faster operations.
    //
    // Numbers with modulo sixty remainder in these lists are known to be composite.
    //
    final HashSet<Integer> fillArray() throws GeneralSecurityException
    {
        // All numbers with modulo-sixty remainder in this list are not prime.
        int[]list1=new int[]{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,
        32,34,36,38,40,42,44,46,48,50,52,54,56,58};        //
        for(int nextInt:list1)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list1");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are  are
        // divisible by three and not prime.
        int[]list2=new int[]{3,9,15,21,27,33,39,45,51,57};
        //
        for(int nextInt:list2)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list2");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are
        // divisible by five and not prime. not prime.
        int[]list3=new int[]{5,25,35,55};
        //
        for(int nextInt:list3)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list3");//
            }
        }
        // All numbers with modulo-sixty remainder in
        // this list have a modulo-four remainder of 1.
        // What that means, I have neither clue nor guess - I got all this from
        int[]list4=new int[]{1,13,17,29,37,41,49,53};
        //
        for(int nextInt:list4)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list4");//
            }
        }
        Integer lowerBound=new Integer(19);// duh
        Double upperStartingPoint=new Double(Math.ceil(Math.sqrt(Integer.MAX_VALUE)));//
        int upperBound=upperStartingPoint.intValue();//
        HashSet<Integer> resultSet=new HashSet<Integer>();
        // use a loop.
        do
        {
            // One of those one liners, whole program here:
            int aModulo=upperBound % 60;
            if(this.hashSet.contains(new Integer(aModulo)))
            {
                continue;
            }
            else
            {
                resultSet.add(new Integer(aModulo));//
            }
        }
        while(--upperBound > 20);
        // this as an operator here is useful later in your work.
        return resultSet;
    }
    // Test harness ....
    public static void main(java.lang.String[] args)
    {
        return;
    }
}
//eof

- Zakir Sajib · Answer 3

要找出前100个素数，可以考虑以下Java代码。

int num = 2;
int i, count;
int nPrimeCount = 0;
int primeCount = 0;

    do
    {

        for (i = 2; i <num; i++)
        {

             int n = num % i;

             if (n == 0) {

             nPrimeCount++;
         //  System.out.println(nPrimeCount + " " + "Non-Prime Number is: " + num);

             num++;
             break;

             }
       }

                if (i == num) {

                    primeCount++;

                    System.out.println(primeCount + " " + "Prime number is: " + num);
                    num++;
                }


     }while (primeCount<100);

- stevenvh · Answer 4

最简单的方法是试错法：您可以尝试2到n-1之间的任何数字来除以您的素数候选n。
首先的快捷方式当然是a）您只需要检查奇数，和b）您只需要检查分隔符是否高达sqrt（n）。

在您的情况下，在该过程中生成了所有先前的素数，因此您只需检查您列表中的任何质数，高达sqrt（n），是否能够除尽n。
这应该是你可以得到的最快速度：-）

编辑
好吧，代码，你要求它。但我警告你:-），这是5分钟快速且肮脏的Delphi代码：

procedure TForm1.Button1Click(Sender: TObject);
const
  N = 100;
var
  PrimeList: TList;
  I, J, SqrtP: Integer;
  Divides: Boolean;
begin
  PrimeList := TList.Create;
  for I := 2 to N do begin
    SqrtP := Ceil(Sqrt(I));
    J := 0;
    Divides := False;
    while (not Divides) and (J < PrimeList.Count) 
                        and (Integer(PrimeList[J]) <= SqrtP) do begin
      Divides := ( I mod Integer(PrimeList[J]) = 0 );
      inc(J);
    end;
    if not Divides then
      PrimeList.Add(Pointer(I));
  end;
  // display results
  for I := 0 to PrimeList.Count - 1 do
    ListBox1.Items.Add(IntToStr(Integer(PrimeList[I])));
  PrimeList.Free;
end;

- grom · Answer 5

这是一个 Python 代码示例，它打印出小于两百万的所有质数的总和：

from math import *

limit = 2000000
sievebound = (limit - 1) / 2
# sieve only odd numbers to save memory
# the ith element corresponds to the odd number 2*i+1
sieve = [False for n in xrange(1, sievebound + 1)]
crosslimit = (int(ceil(sqrt(limit))) - 1) / 2
for i in xrange(1, crosslimit):
    if not sieve[i]:
        # if p == 2*i + 1, then
        #   p**2 == 4*(i**2) + 4*i + 1
        #        == 2*i * (i + 1)
        for j in xrange(2*i * (i + 1), sievebound, 2*i + 1):
            sieve[j] = True
sum = 2
for i in xrange(1, sievebound):
    if not sieve[i]:
        sum = sum + (2*i+1)
print sum