前 10000 个素数最有效的代码？

https://stackoverflow.com/questions/622

08-06-2019
|

题

我想打印前 10000 个素数。谁能给我最有效的代码？澄清：

如果您的代码在 n >10000 时效率低下，那也没关系。
代码的大小并不重要。
您不能以任何方式对值进行硬编码。

解决方案

阿特金筛可能就是您正在寻找的，它的运行时间上限是 O(N/log log N)。

如果只运行比 6 的倍数多 1 和少 1 的数字，速度可能会更快，因为 3 以上的所有素数与 6 的倍数相差 1。我的声明的资源

其他提示

我推荐一个筛子，无论是埃拉托斯特尼筛法或者阿特金筛。

筛法或埃拉托色尼可能是查找素数列表最直观的方法。基本上你：

写下一个从 2 到任何你想要的限制的数字列表，假设是 1000。
取出第一个未划掉的数字（对于第一次迭代，这是 2）并从列表中划掉该数字的所有倍数。
重复步骤 2，直到到达列表末尾。所有没有划掉的数字都是素数。

显然，可以进行很多优化来使该算法运行得更快，但这是基本思想。

阿特金筛法使用了类似的方法，但不幸的是我对此了解不够，无法向您解释。但我确实知道我链接的算法需要 8 秒才能在古老的 Pentium II-350 上计算出 1000000000 以内的所有素数

埃拉托色尼筛源代码： http://web.archive.org/web/20140705111241/http://primes.utm.edu/links/programs/sieves/Eratosthenes/C_source_code/

阿特金筛源代码： http://cr.yp.to/primegen.html

这并不严格违反硬编码限制，但非常接近。为什么不以编程方式下载此列表并将其打印出来呢？

http://primes.utm.edu/lists/small/10000.txt

门杀手, ，添加一个如何 break 对此 if 在里面 foreach 环形？这会加快速度很多因为如果 6 能被 2 整除，则不需要检查 3 和 5。（如果我有足够的声誉，我无论如何都会投票支持你的解决方案:-) ...）

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
            break;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

在 Haskell 中，我们几乎可以逐字写下埃拉托色尼筛的数学定义，“素数是大于 1 的自然数，没有任何合数，其中合数是通过枚举每个素数的倍数来找到的":

primes = 2 : minus [3..] (foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r)
                                [] primes)

primes !! 10000 几乎是瞬时的。

参考：

_{上面的代码很容易调整为仅处理赔率， primes = 2 : 3 : minus [5,7..] (foldr (\p r -> p*p : union [p*p+2*p, p*p+4*p..] r) [] (tail primes)). 。时间复杂度大大提高（大约为日志最佳因子）通过折叠成树状结构，空间复杂度为大大改善经过多级素数产生, ，在}

primes = 2 : _Y ( (3:) . sieve 5 . _U . map (\p -> [p*p, p*p+2*p..]) )
  where
    _Y g = g (_Y g)                        -- non-sharing fixpoint combinator
    _U ((x:xs):t) = x : (union xs . _U . pairs) t       -- ~= nub.sort.concat
    pairs    (xs:ys:t)  = union xs ys : pairs t
    sieve k s@(x:xs) | k < x      = k : sieve (k+2) s   -- ~= [k,k+2..]\\s,
                     | otherwise  =     sieve (k+2) xs  --   when s⊂[k,k+2..]

_{（在 Haskell 中，括号用于分组，函数调用仅通过并置来表示， (:) 是一个缺点列表运算符，以及 (.) 是一个函数复合运算符： (f . g) x = (\y -> f (g y)) x = f (g x)).}

@马特：log(log(10000)) 约为 2

来自维基百科文章（您引用的）阿特金筛:

此筛分计算最多使用n的素数 O(N/log log N) 只有n的操作^1/2+o(1) 内存位。这比使用的Eratosthenes的筛子要好一点 O(N)操作和 O(N^1/2（日志n）/log n）内存的位（A.O.L.阿特金，D.J.伯恩斯坦，2004）. 。这些渐近计算复杂性包括简单的优化，例如车轮分解，并将计算分解为较小的块。

给定渐近计算复杂度 O(N) （对于埃拉托色尼）和 O(N/log(log(N))) （对于阿特金）我们不能说（对于小 N=10_000）如果实施哪种算法会更快。

阿奇姆·弗拉门坎普 (Achim Flammenkamp) 写道埃拉托色尼筛法:

被引用：

@num1

对于大约10^9的间隔，对于> 10^10的时间肯定，eratosthenes的筛子的表现超过了Atkins和Bernstein的筛子，而Atkins和Bernstein使用了不可约合的二进制二进制形式。有关背景信息以及W的第5段，请参阅他们的论文。戈尔韦的博士学位论文。

因此对于 10_000 埃拉托色尼筛法比阿特金筛法更快。

要回答OP，代码是 prime_sieve.c （被引用 num1)

使用 GMP，可以编写以下内容：

#include <stdio.h>
#include <gmp.h>

int main() {
  mpz_t prime;
  mpz_init(prime);
  mpz_set_ui(prime, 1);
  int i;
  char* num = malloc(4000);
  for(i=0; i<10000; i++) {
    mpz_nextprime(prime, prime);
    printf("%s, ", mpz_get_str(NULL,10,prime));
  }
}

在我的 2.33GHz Macbook Pro 上，它执行如下：

time ./a.out > /dev/null

real    0m0.033s
user    0m0.029s
sys    0m0.003s

在同一台笔记本电脑上计算 1,000,000 个素数：

time ./a.out > /dev/null

real    0m14.824s
user    0m14.606s
sys     0m0.086s

GMP 针对此类事情进行了高度优化。除非您真的想通过编写自己的算法来理解算法，否则建议您在 C 下使用 libGMP。

效率很低，但您可以使用正则表达式来测试素数。

/^1?$|^(11+?)\1+$/

这测试是否对于由以下组成的字符串 k “1” 的， k 是 不是素数 （IE。字符串是否由一个“组成”1” 或任意数量的“1” 可以表示为 n- 元产品）。

我已经改编了在代码项目创建以下内容：

ArrayList primeNumbers = new ArrayList();

for(int i = 2; primeNumbers.Count < 10000; i++) {
    bool divisible = false;

    foreach(int number in primeNumbers) {
        if(i % number == 0) {
            divisible = true;
        }
    }

    if(divisible == false) {
        primeNumbers.Add(i);
        Console.Write(i + " ");
    }
}

在我的 ASP.NET 服务器上测试此例程大约需要 1 分钟。

这是我几天前在 PowerShell 中编写的埃拉托斯特尼筛法。它有一个参数用于标识应返回的素数的数量。

#
# generate a list of primes up to a specific target using a sieve of eratosthenes
#
function getPrimes { #sieve of eratosthenes, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    param ($target,$count = 0)
    $sieveBound = [math]::ceiling(( $target - 1 ) / 2) #not storing evens so count is lower than $target
    $sieve = @($false) * $sieveBound
    $crossLimit = [math]::ceiling(( [math]::sqrt($target) - 1 ) / 2)
    for ($i = 1; $i -le $crossLimit; $i ++) {
        if ($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Found: $prime"
            for ($x = 2 * $i * ( $i + 1 ); $x -lt $sieveBound; $x += 2 * $i + 1) {
                $sieve[$x] = $true
            }
        }
    }
    $primes = @(2)
    for ($i = 1; $i -le $sieveBound; $i ++) {
        if($count -gt 0 -and $primes.length -ge $count) {
            break;
        }
        if($sieve[$i] -eq $false) {
            $prime = 2 * $i + 1
            write-debug "Output: $prime"
            $primes += $prime
        }
    }
    return $primes
}

埃拉托斯特尼筛法是可行的方法，因为它简单且速度快。我在C中的实现

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void)
{
    unsigned int lim, i, j;

    printf("Find primes upto: ");
    scanf("%d", &lim);
    lim += 1;
    bool *primes = calloc(lim, sizeof(bool));

    unsigned int sqrtlim = sqrt(lim);
    for (i = 2; i <= sqrtlim; i++)
        if (!primes[i])
            for (j = i * i; j < lim; j += i)
                primes[j] = true;

    printf("\nListing prime numbers between 2 and %d:\n\n", lim - 1);
    for (i = 2; i < lim; i++)
        if (!primes[i])
            printf("%d\n", i);

    return 0;
}

查找素数的 CPU 时间（在 Pentium Dual Core E2140 1.6 GHz 上，使用单核）

~ 4s for lim = 100,000,000

适应并遵循门杀手, ，这是我使用的最终版本。

    public IEnumerable<long> PrimeNumbers(long number)
    {
        List<long> primes = new List<long>();
        for (int i = 2; primes.Count < number; i++)
        {
            bool divisible = false;

            foreach (int num in primes)
            {
                if (i % num == 0)
                    divisible = true;

                if (num > Math.Sqrt(i))
                    break;
            }

            if (divisible == false)
                primes.Add(i);
        }
        return primes;
    }

它基本上是相同的，但我添加了“break on Sqrt”建议并更改了一些变量以使其更适合我。（我正在研究欧拉并需要第 10001 个素数）

筛子似乎是错误的答案。筛子给你素数 取决于 一个号码氮, ，不是 第一个N 素数。运行@Imran 或@Andrew Szeto，你会得到N 以内的素数。

如果您继续尝试对越来越大的数字进行筛选，直到达到结果集的一定大小，并使用已获得的数字的一些缓存，则该筛子可能仍然可用，但我相信它仍然不会比 @Pat 这样的解决方案更快。

在Python中

import gmpy
p=1
for i in range(10000):
    p=gmpy.next_prime(p)
    print p

这 BenGoldberg 提到的 deque sieve 算法值得仔细研究，不仅因为它非常优雅，而且因为它在实践中偶尔有用（与阿特金筛法不同，后者纯粹是学术练习）。

双端队列筛选算法背后的基本思想是使用一个小的滑动筛子，该筛子的大小仅足以包含每个当前“活动”素数因子的至少一个单独的倍数 - 即平方不超过当前移动筛子所代表的最小数的那些素数。与 SoE 的另一个区别是，双端队列筛选器将实际因子存储到复合槽中，而不是布尔值。

该算法根据需要扩展筛子窗口的大小，从而在很宽的范围内获得相当均匀的性能，直到筛子开始明显超过 CPU 的 L1 缓存的容量。最后一个完全拟合的素数是 25,237,523（第 1,579,791 个素数），它给出了算法合理运行范围的粗略数字。

该算法相当简单且稳健，甚至比未分段的埃拉托斯特尼筛法的性能范围更广。只要后者的筛子完全适合缓存，即后者会快得多。对于具有字节大小 bool 的仅赔率筛选，最多为 2^16。然后它的性能下降得越来越多，尽管它总是比双端队列快得多，尽管有障碍（至少在 C/C++、Pascal 或 Java/C# 等编译语言中）。

这是用 C# 呈现的双端队列筛选算法，因为我发现这种语言（尽管有很多缺陷）对于原型算法和实验来说比极其繁琐和迂腐的 C++ 更实用。（边注：我正在使用免费的 LINQPad 这使得我可以直接投入使用，而无需设置项目、makefile、目录或诸如此类的混乱，并且它为我提供了与 python 提示相同程度的交互性）。

C# 没有显式的双端队列类型，但有普通的 List<int> 对于演示该算法来说效果很好。

笔记：这个版本没有对素数使用双端队列，因为从 n 个素数中弹出 sqrt(n) 根本没有意义。去掉 100 个素数，留下 9900 个素数有什么好处呢？至少通过这种方式，所有素数都被收集在一个整齐的向量中，准备进一步处理。

static List<int> deque_sieve (int n = 10000)
{
    Trace.Assert(n >= 3);

    var primes = new List<int>()  {  2, 3  };
    var sieve = new List<int>()  {  0, 0, 0  };

    for (int sieve_base = 5, current_prime_index = 1, current_prime_squared = 9; ; )
    {
        int base_factor = sieve[0];

        if (base_factor != 0)
        {
            // the sieve base has a non-trivial factor - put that factor back into circulation
            mark_next_unmarked_multiple(sieve, base_factor);
        }
        else if (sieve_base < current_prime_squared)  // no non-trivial factor -> found a non-composite
        {
            primes.Add(sieve_base);

            if (primes.Count == n)
                return primes;
        }
        else // sieve_base == current_prime_squared
        {
            // bring the current prime into circulation by injecting it into the sieve ...
            mark_next_unmarked_multiple(sieve, primes[current_prime_index]);

            // ... and elect a new current prime
            current_prime_squared = square(primes[++current_prime_index]);
        }

        // slide the sieve one step forward
        sieve.RemoveAt(0);  sieve_base += 2;
    }
}

这是两个辅助函数：

static void mark_next_unmarked_multiple (List<int> sieve, int prime)
{
    int i = prime, e = sieve.Count;

    while (i < e && sieve[i] != 0)
        i += prime;

    for ( ; e <= i; ++e)  // no List<>.Resize()...
        sieve.Add(0);

    sieve[i] = prime;
}

static int square (int n)
{
    return n * n;
}

理解该算法的最简单方法可能是将其想象为一个特殊的分段埃拉托斯特尼筛，分段大小为 1，并伴有一个溢出区域，当素数射过分段末端时，素数会在溢出区域中停下来。除了该段的单个单元格（又名： sieve[0]当我们到达它时，它已经被筛分了，因为它在溢出区域的时候被碾过。

所代表的数字 sieve[0] 举行于 sieve_base, ，虽然 sieve_front 或者 window_base 也将是一个好名字，可以与 Ben 的代码或分段/窗口筛的实现进行比较。

如果 sieve[0] 包含一个非零值，那么该值是 sieve_base, ，因此可以被认为是复合的。由于单元 0 是该因子的倍数，因此很容易计算其下一跳，即 0 加该因子。如果该单元格已经被另一个因子占据，那么我们只需再次添加该因子，依此类推，直到我们找到当前没有其他因子停放的因子的倍数（如果需要，则扩展筛子）。这也意味着不需要像普通分段筛那样存储从一个分段到下一个分段的各种素数的当前工作偏移量。每当我们发现一个因素 sieve[0], ，其当前工作偏置为0。

当前的素数通过以下方式发挥作用。素数只有在它自己出现在流中后才能成为当前素数（即。当它被检测为素数时，因为没有标记因子），并且它将保持当前状态，直到出现的确切时刻 sieve[0] 到达它的正方形。由于较小素数的活动，该素数的所有较低倍数必定已被删除，就像在正常的 SoE 中一样。但是较小的素数都不能消除正方形，因为正方形的唯一因子是素数本身，并且此时它尚未流通。这解释了算法在这种情况下采取的行动 sieve_base == current_prime_squared （这意味着 sieve[0] == 0, ，顺便一提）。

现在的情况 sieve[0] == 0 && sieve_base < current_prime_squared 很容易解释：代表着 sieve_base 不能是任何小于当前素数的倍数，否则它会被标记为合数。I 也不能是当前素数的更高倍数，因为它的值小于当前素数的平方。因此它一定是一个新素数。

该算法显然是受到埃拉托斯特尼筛法的启发，但同样明显的是它有很大不同。埃拉托斯特尼筛法的卓越速度源自其基本运算的简单性：它在很长一段时间内所做的只是添加一个索引并为操作的每一步存储一次。

这是一个简单的、不分段的埃拉托色尼筛法，我通常用它来筛选 ushort 范围内的因子素数，即最多 2^16。对于这篇文章，我通过替换将其修改为超过 2^16 int 为了 ushort

static List<int> small_odd_primes_up_to (int n)
{
    var result = new List<int>();

    if (n < 3)
        return result;

    int sqrt_n_halved = (int)(Math.Sqrt(n) - 1) >> 1, max_bit = (n - 1) >> 1;
    var odd_composite = new bool[max_bit + 1];

    for (int i = 3 >> 1; i <= sqrt_n_halved; ++i)
        if (!odd_composite[i])
            for (int p = (i << 1) + 1, j = p * p >> 1; j <= max_bit; j += p)
                odd_composite[j] = true;

    result.Add(3);  // needs to be handled separately because of the mod 3 wheel

    // read out the sieved primes
    for (int i = 5 >> 1, d = 1; i <= max_bit; i += d, d ^= 3)
        if (!odd_composite[i])
            result.Add((i << 1) + 1);

    return result;
}

当筛选前 10000 个素数时，将超出 32 KiByte 的典型 L1 缓存，但该函数仍然非常快（即使在 C# 中也只有几分之一毫秒）。

如果将此代码与双端队列筛选器进行比较，那么很容易发现双端队列筛选器的操作要复杂得多，并且它不能有效地摊销其开销，因为它总是在一行中进行尽可能短的交叉延伸（在跳过所有已被划掉的倍数之后，正好划掉一个）。

笔记：C# 代码使用 int 代替 uint 因为较新的编译器有生成不标准代码的习惯 uint, ，可能是为了推动人们使用有符号整数......在上面代码的 C++ 版本中我使用了 unsigned 自然地，自始至终；基准测试必须采用 C++ 语言，因为我希望它基于一个足够的双端队列类型（std::deque<unsigned>;使用没有任何性能提升 unsigned short）。以下是我的 Haswell 笔记本电脑 (VC++ 2015/x64) 的编号：

deque vs simple: 1.802 ms vs 0.182 ms
deque vs simple: 1.836 ms vs 0.170 ms 
deque vs simple: 1.729 ms vs 0.173 ms

笔记：C# 时间几乎是 C++ 时间的两倍，这对于 C# 来说非常好，并且 ìt 表明 List<int> 即使被滥用为双端队列，它也毫不逊色。

即使双端队列已经超出其正常工作范围（L1 缓存大小超过 50%，伴随着缓存抖动），简单的筛选代码仍然可以将双端队列从水中剔除。这里的主要部分是读取筛选的素数，这并不受缓存问题的影响。在任何情况下，该函数都是为了筛选因素中的因素而设计的，即3 级筛选层次结构中的第 0 级，通常它只需返回几百个因子或几千个因子。因此它很简单。

通过使用分段筛并优化提取筛分素数的代码（步进 mod 3 并展开两次，或 mod 15 并展开一次），性能可以提高一个数量级以上，而且还可以挤出更多性能通过使用带有所有装饰的 mod 16 或 mod 30 车轮来编写代码（即完全展开所有残留物）。我的回答中解释了类似的事情找到素数位置的素数在 Code Review 上，讨论了类似的问题。但很难看出为一次性任务改进亚毫秒时间有什么意义……

为了更客观地看待问题，以下是筛选最多 100,000,000 的 C++ 时序：

deque vs simple: 1895.521 ms vs 432.763 ms
deque vs simple: 1847.594 ms vs 429.766 ms
deque vs simple: 1859.462 ms vs 430.625 ms

相比之下，带有一些附加功能的 C# 分段筛在 95 毫秒内完成了相同的工作（没有可用的 C++ 计时，因为我目前仅在 C# 中进行代码挑战）。

在像 Python 这样的解释性语言中，事情可能看起来截然不同，其中每个操作都有很大的成本，并且解释器开销使所有由于预测与预测而产生的差异相形见绌。错误预测的分支或子循环操作（移位、加法）与错误预测的分支或子循环操作（移位、加法）对比多周期运算（乘法，甚至除法）。这势必会削弱埃拉托斯特尼筛法的简单性优势，而这可能会使双端队列解决方案更具吸引力。

此外，其他受访者在该主题中报告的许多时间可能主要是 输出时间. 。那是一场完全不同的战争，我的主要武器是一个像这样的简单类：

class CCWriter
{
    const int SPACE_RESERVE = 11;  // UInt31 + '\n'

    public static System.IO.Stream BaseStream;
    static byte[] m_buffer = new byte[1 << 16];  // need 55k..60k for a maximum-size range
    static int m_write_pos = 0;
    public static long BytesWritten = 0;         // for statistics

    internal static ushort[] m_double_digit_lookup = create_double_digit_lookup();

    internal static ushort[] create_double_digit_lookup ()
    {
        var lookup = new ushort[100];

        for (int lo = 0; lo < 10; ++lo)
            for (int hi = 0; hi < 10; ++hi)
                lookup[hi * 10 + lo] = (ushort)(0x3030 + (hi << 8) + lo);

        return lookup;
    }

    public static void Flush ()
    {
        if (BaseStream != null && m_write_pos > 0)
            BaseStream.Write(m_buffer, 0, m_write_pos);

        BytesWritten += m_write_pos;
        m_write_pos = 0;
    }

    public static void WriteLine ()
    {
        if (m_buffer.Length - m_write_pos < 1)
            Flush();

        m_buffer[m_write_pos++] = (byte)'\n';
    }

    public static void WriteLinesSorted (int[] values, int count)
    {
        int digits = 1, max_value = 9;

        for (int i = 0; i < count; ++i)
        {
            int x = values[i];

            if (m_buffer.Length - m_write_pos < SPACE_RESERVE)
                Flush();

            while (x > max_value)
                if (++digits < 10)
                    max_value = max_value * 10 + 9;
                else
                    max_value = int.MaxValue;               

            int n = x, p = m_write_pos + digits, e = p + 1;

            m_buffer[p] = (byte)'\n';

            while (n >= 10)
            {
                int q = n / 100, w = m_double_digit_lookup[n - q * 100];
                n = q;
                m_buffer[--p] = (byte)w;
                m_buffer[--p] = (byte)(w >> 8);
            }

            if (n != 0 || x == 0)
                m_buffer[--p] = (byte)((byte)'0' + n);

            m_write_pos = e;
        }
    }
}

写入 10000 个（已排序的）数字只需不到 1 毫秒。它是一个静态类，因为它旨在将文本包含在编码挑战提交中，以最少的麻烦和零开销。

一般来说，我发现它是很多如果集中工作在整个批次上完成，则速度会更快，这意味着筛选某个范围，然后将所有素数提取到向量/数组中，然后爆破整个数组，然后筛选下一个范围等等，而不是将所有内容混合在一起。拥有专注于特定任务的单独功能还可以更轻松地混合和匹配，实现重用，并简化开发/测试。

这是我的 VB 2008 代码，它在我的工作笔记本电脑上在 1 分 27 秒内找到所有 <10,000,000 的素数。它会跳过偶数，只查找 < 测试数的 sqrt 的素数。它仅设计用于查找从 0 到哨兵值的素数。

Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles 
Button1.Click

    Dim TestNum As Integer
    Dim X As Integer
    Dim Z As Integer
    Dim TM As Single
    Dim TS As Single
    Dim TMS As Single
    Dim UnPrime As Boolean
    Dim Sentinal As Integer
    Button1.Text = "Thinking"
    Button1.Refresh()
    Sentinal = Val(SentinalTxt.Text)
    UnPrime = True
    Primes(0) = 2
    Primes(1) = 3
    Z = 1
    TM = TimeOfDay.Minute
    TS = TimeOfDay.Second
    TMS = TimeOfDay.Millisecond
    For TestNum = 5 To Sentinal Step 2
        Do While Primes(X) <> 0 And UnPrime And Primes(X) ^ 2 <= TestNum
            If Int(TestNum / Primes(X)) - (TestNum / Primes(X)) = 0 Then
                UnPrime = False
            End If
            X = X + 1

        Loop
        If UnPrime = True Then
            X = X + 1
            Z = Z + 1
            Primes(Z) = TestNum
        End If
        UnPrime = True
        X = 0
    Next
    Button1.Text = "Finished with " & Z
    TM = TimeOfDay.Minute - TM
    TS = TimeOfDay.Second - TS
    TMS = TimeOfDay.Millisecond - TMS
    ShowTime.Text = TM & ":" & TS & ":" & TMS
End Sub

以下 Mathcad 代码在 3 分钟内计算出前一百万个素数。

请记住，这将对所有数字使用浮点双精度，并且基本上是解释的。我希望语法是清楚的。

enter image description here

这是一个使用 SoE 形式的 C++ 解决方案：

#include <iostream>
#include <deque>

typedef std::deque<int> mydeque;

void my_insert( mydeque & factors, int factor ) {
    int where = factor, count = factors.size();
    while( where < count && factors[where] ) where += factor;
    if( where >= count ) factors.resize( where + 1 );
    factors[ where ] = factor;
}

int main() {
    mydeque primes;
    mydeque factors;
    int a_prime = 3, a_square_prime = 9, maybe_prime = 3;
    int cnt = 2;
    factors.resize(3);
    std::cout << "2 3 ";

    while( cnt < 10000 ) {
        int factor = factors.front();
        maybe_prime += 2;
        if( factor ) {
            my_insert( factors, factor );
        } else if( maybe_prime < a_square_prime ) {
            std::cout << maybe_prime << " ";
            primes.push_back( maybe_prime );
            ++cnt;
        } else {
            my_insert( factors, a_prime );
            a_prime = primes.front();
            primes.pop_front();
            a_square_prime = a_prime * a_prime;
        }
        factors.pop_front();
    }

    std::cout << std::endl;
    return 0;
}

请注意，此版本的筛子可以无限地计算素数。

另请注意，STL deque 需要 O(1) 表演时间 push_back, pop_front, ，并通过下标进行随机访问。

这 resize 操作需要 O(n) 时间、地点 n 是添加的元素数量。由于我们如何使用这个函数，我们可以将其视为一个小常量。

的身体 while 循环进入 my_insert 被执行 O(log log n) 时间、地点 n 等于变量 maybe_prime. 。这是因为条件表达式 while 将为每个质因数评估一次为真 maybe_prime. 。看 ”除数函数”在维基百科上。

乘以次数 my_insert 被调用，表明它应该采取 O(n log log n) 列出时间 n 素数...毫不奇怪，这就是埃拉托色尼筛法应该具有的时间复杂度。

然而，虽然这段代码是高效，这不是 最有效率的...我强烈建议使用专门的库来生成素数，例如初筛. 。任何真正高效、优化良好的解决方案都需要比任何人想要在 Stackoverflow 中输入的代码还要多的代码。

与“已知范围内”的素数算法相比，使用埃拉托斯特尼筛法的计算速度要快得多。

通过使用维基百科中的伪代码（https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes），我能够在 C# 上找到解决方案。

/// Get non-negative prime numbers until n using Sieve of Eratosthenes.
public int[] GetPrimes(int n) {
    if (n <= 1) {
        return new int[] { };
    }

    var mark = new bool[n];
    for(var i = 2; i < n; i++) {
        mark[i] = true;
    }

    for (var i = 2; i < Math.Sqrt(n); i++) {
        if (mark[i]) {
            for (var j = (i * i); j < n; j += i) {
                mark[j] = false;
            }
        }
    }

    var primes = new List<int>();
    for(var i = 3; i < n; i++) {
        if (mark[i]) {
            primes.Add(i);
        }
    }

    return primes.ToArray();
}

GetPrimes(100000000) 需要 2 秒 330 毫秒。

笔记: ：值可能因硬件规格而异。

我花了一些时间编写一个计算大量素数的程序，这是我用来计算包含前 1.000.000.000 个素数的文本文件的代码。它是德语的，但有趣的是方法 calcPrimes(). 。素数存储在名为 Primzahlen 的数组中。我推荐使用 64 位 CPU，因为计算使用 64 位整数。

import java.io.*;
class Primzahlengenerator {
    long[] Primzahlen;
    int LastUnknown = 2;
    public static void main(String[] args)  {
        Primzahlengenerator Generator = new Primzahlengenerator();
        switch(args.length) {
            case 0:  //Wenn keine Argumente übergeben worden:
                Generator.printHelp(); //Hilfe ausgeben
                return; //Durchfallen verhindern
            case 1:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                    //Generelle Hilfe ausgeben
                    return;
                }
                break;//dutchfallen verhindern

            case 2:
                switch (args[1]) {
                    case "-l":
                        System.out.println("Sie müsen auch eine Datei angeben!"); //Hilfemitteilung ausgeben
                        Generator.printHelp();                                    //Generelle Hilfe ausgeben
                        return;
                }
                break;//durchfallen verhindern
            case 3:
                try {
                    Generator.Primzahlen = new long[Integer.decode(args[0]).intValue()];
                }
                catch (NumberFormatException e) {
                    System.out.println("Das erste Argument muss eine Zahl sein, und nicht als Wort z.B. \"Tausend\", sondern in Ziffern z.B. \"1000\" ausgedrückt werden.");//Hinweis, wie man die Argumente angeben muss ausgeben
                    Generator.printHelp();                      //Generelle Hilfe ausgeben
                    return;
                }
                switch(args[1]) {
                    case "-l":
                        Generator.loadFromFile(args[2]);//Datei Namens des Inhalts von Argument 3 lesen, falls Argument 2 = "-l" ist
                        break;
                    default:
                        Generator.printHelp();
                        break;
                }
                break;
            default:
                Generator.printHelp();
                return;
        }
        Generator.calcPrims();
    }
    void printHelp() {
        System.out.println("Sie müssen als erstes Argument angeben, die wieviel ersten Primzahlen sie berechnen wollen.");   //Anleitung wie man das Programm mit Argumenten füttern muss
        System.out.println("Als zweites Argument können sie \"-l\" wählen, worauf die Datei, aus der die Primzahlen geladen werden sollen,");
        System.out.println("folgen muss. Sie muss genauso aufgebaut sein, wie eine Datei Primzahlen.txt, die durch den Aufruf \"java Primzahlengenerator 1000 > Primzahlen.txt\" entsteht.");
    }
    void loadFromFile(String File) {
        // System.out.println("Lese Datei namens: \"" + File + "\"");
        try{
            int x = 0;
            BufferedReader in = new BufferedReader(new FileReader(File));
            String line;
            while((line = in.readLine()) != null) {
                Primzahlen[x] = new Long(line).longValue();
                x++;
            }
            LastUnknown = x;
        } catch(FileNotFoundException ex) {
            System.out.println("Die angegebene Datei existiert nicht. Bitte geben sie eine existierende Datei an.");
        } catch(IOException ex) {
            System.err.println(ex);
        } catch(ArrayIndexOutOfBoundsException ex) {
            System.out.println("Die Datei enthält mehr Primzahlen als der reservierte Speicherbereich aufnehmen kann. Bitte geben sie als erstes Argument eine größere Zahl an,");
            System.out.println("damit alle in der Datei enthaltenen Primzahlen aufgenommen werden können.");
            }
        /* for(long prim : Primzahlen) {
            System.out.println("" + prim);
        } */
        //Hier soll code stehen, der von der Datei mit angegebenem Namen ( Wie diese aussieht einfach durch angeben von folgendem in cmd rausfinden:
        //java Primzahlengenerator 1000 > 1000Primzahlen.txt
        //da kommt ne textdatei, die die primzahlen enthält. mit Long.decode(String ziffern).longValue();
        //erhält man das was an der entsprechenden stelle in das array soll. die erste zeile soll in [0] , die zweite zeile in [1] und so weiter.
        //falls im arry der platz aus geht(die exception kenn ich grad nich, aber mach mal:
        //int[] foo = { 1, 2, 3};
        //int bar = foo[4];
        //dann kriegst ne exception, das ist die gleiche die man kriegt, wenn im arry der platzt aus geht.
    }
    void calcPrims() {
        int PrimzahlNummer = LastUnknown;
        // System.out.println("LAstUnknown ist: " + LastUnknown);
        Primzahlen[0] = 2;
        Primzahlen[1] = 3;
        long AktuelleZahl = Primzahlen[PrimzahlNummer - 1];
        boolean IstPrimzahl;
        // System.out.println("2");
        // System.out.println("3");
        int Limit = Primzahlen.length;
        while(PrimzahlNummer < Limit) {
            IstPrimzahl = true;
            double WurzelDerAktuellenZahl = java.lang.Math.sqrt(AktuelleZahl);
            for(int i = 1;i < PrimzahlNummer;i++) {
                if(AktuelleZahl % Primzahlen[i] == 0) {
                    IstPrimzahl = false;
                    break;
                }
                if(Primzahlen[i] > WurzelDerAktuellenZahl) break;
            }
            if(IstPrimzahl) {
                Primzahlen[PrimzahlNummer] = AktuelleZahl;
                PrimzahlNummer++;
                // System.out.println("" + AktuelleZahl);
            }
            AktuelleZahl = AktuelleZahl + 2;
        }
        for(long prim : Primzahlen) {
            System.out.println("" + prim);
        }
    }
}

我是用 python 写的，因为我刚刚开始学习它，它工作得很好。此代码生成的第 10,000 个素数与中提到的相同 http://primes.utm.edu/lists/small/10000.txt. 。检查是否 n 是否素数，除以 n 由数字 2 到 sqrt(n). 。如果这个范围内的任何一个数字能完全整除 n 那么它就不是素数了。

import math
print ("You want prime till which number??")
a = input()
a = int(a)
x = 0
x = int(x)
count = 1
print("2 is prime number")
for c in range(3,a+1):
    b = math.sqrt(c)
    b = int(b)
    x = 0
    for b in range(2,b+1):
        e  = c % b
        e = int(e)
        if (e == 0):
            x = x+1
    if (x == 0):
        print("%d is prime number" % c)
        count = count + 1
print("Total number of prime till %d is %d" % (a,count))

我从事寻找素数工作大约一年了。这是我发现最快的：

import static java.lang.Math.sqrt;
import java.io.PrintWriter;
import java.io.File;
public class finder {
    public static void main(String[] args) {
        primelist primes = new primelist();
        primes.insert(3);
        primes.insert(5);
        File file = new File("C:/Users/Richard/Desktop/directory/file0024.txt");
        file.getParentFile().mkdirs();
        long time = System.nanoTime();
        try{
            PrintWriter printWriter = new PrintWriter ("file0024.txt"); 
            int linenum = 0;
            printWriter.print("2");
            printWriter.print (" , ");
            printWriter.print("3");
            printWriter.print (" , ");
            int up;
            int down;           
            for(int i =1; i<357913941;i++){//
                if(linenum%10000==0){
                    printWriter.println ("");
                    linenum++;
                }
                down = i*6-1;
                if(primes.check(down)){
                    primes.insert(down);
                    //System.out.println(i*6-1);
                    printWriter.print ( down );
                    printWriter.print (" , ");
                    linenum++;  
                }
                up = i*6+1;
                if(primes.check(up)){
                    primes.insert(up);
                    //System.out.println(i*6+1);
                    printWriter.print ( up );
                    printWriter.print (" , ");
                    linenum++;  
                }
            }
            printWriter.println ("Time to execute");
            printWriter.println (System.nanoTime()-time);
            //System.out.println(primes.length);
            printWriter.close ();
        }catch(Exception e){}
    } 
}
class node{
    node next;
    int x;
    public node (){
        node next;
        x = 3;
    }
    public node(int z) {
        node next;
        x = z;
    }
}
class primelist{
    node first;
    int length =0;
    node current;
    public void insert(int x){
        node y = new node(x);
        if(current == null){
            current = y;
            first = y;
        }else{
            current.next = y;
            current = y;
        }
        length++;
    }
    public boolean check(int x){
        int p = (int)sqrt(x);
        node y = first;
        for(int i = 0;i<length;i++){
            if(y.x>p){
                return true;
            }else if(x%y.x ==0){
                return false;
            }
            y = y.next;
        }
        return true;
    }
}

从 2 开始到 2147483629 需要 1902465190909 纳秒。

这是我的代码，它在我的笔记本电脑上找到了0.049655秒的首个10,000个素数，在6秒内首批1,000,000个素数，在15秒内首批2,000,000
一点解释。该方法使用两种技术来查找素数

首先，任何非素数都是素数倍数的组合，因此此代码测试通过将测试数除以较小的素数而不是任何数字来进行测试，对于 4 位数字，这可以减少至少 10 倍的计算量，对于更大的数字
其次，除了除以素数之外，它只除以小于或等于被测试数的根的素数，这进一步大大减少了计算量，这是有效的，因为任何大于该数的根的数都会有一个对应的数必须小于数字的根，但由于我们已经测试了所有小于根的数字，因此我们不需要担心大于被测试数字的根的数字。

前 10,000 个素数的示例输出
https://drive.google.com/open?id=0B2QYXBiLI-lZMUpCNFhZeUphck0 https://drive.google.com/open?id=0B2QYXBiLI-lZbmRtTkZETnp6Ykk

这是C语言的代码，输入1，然后输入10,000，以打印出前10,000个素数。
编辑：我忘记这包含数学库，如果你在 Windows 或 Visual Studio 上，那应该没问题，但在 Linux 上，你必须使用 -lm 参数编译代码，否则代码可能无法工作
例子：gcc -Wall -o "%e" "%f" -lm

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>

/* Finding prime numbers */
int main()
{   
    //pre-phase
    char d,w;
    int l,o;
    printf("  1. Find first n number of prime numbers or Find all prime numbers smaller than n ?\n"); // this question helps in setting the limits on m or n value i.e l or o 
    printf("     Enter 1 or 2 to get anwser of first or second question\n");
    // decision making
    do
    {
        printf("  -->");
        scanf("%c",&d);
        while ((w=getchar()) != '\n' && w != EOF);
        if ( d == '1')
        {
            printf("\n  2. Enter the target no. of primes you will like to find from 3 to 2,000,000 range\n  -->");
            scanf("%10d",&l);
            o=INT_MAX;
            printf("  Here we go!\n\n");
            break;
        }
        else if ( d == '2' )
        {
            printf("\n  2.Enter the limit under which to find prime numbers from 5 to 2,000,000 range\n  -->");
            scanf("%10d",&o);
            l=o/log(o)*1.25;
            printf("  Here we go!\n\n");
            break;
        }
        else printf("\n  Try again\n");
    }while ( d != '1' || d != '2' );

    clock_t start, end;
    double cpu_time_used;
    start = clock(); /* starting the clock for time keeping */

    // main program starts here
    int i,j,c,m,n; /* i ,j , c and m are all prime array 'p' variables and n is the number that is being tested */
    int s,x;

    int p[ l ]; /* p is the array for storing prime numbers and l sets the array size, l was initialized in pre-phase */
    p[1]=2;
    p[2]=3;
    p[3]=5;
    printf("%10dst:%10d\n%10dnd:%10d\n%10drd:%10d\n",1,p[1],2,p[2],3,p[3]); // first three prime are set
    for ( i=4;i<=l;++i ) /* this loop sets all the prime numbers greater than 5 in the p array to 0 */
        p[i]=0;

    n=6; /* prime number testing begins with number 6 but this can lowered if you wish but you must remember to update other variables too */
    s=sqrt(n); /* 's' does two things it stores the root value so that program does not have to calaculate it again and again and also it stores it in integer form instead of float*/
    x=2; /* 'x' is the biggest prime number that is smaller or equal to root of the number 'n' being tested */

    /* j ,x and c are related in this way, p[j] <= prime number x <= p[c] */

    // the main loop begins here
    for ( m=4,j=1,c=2; m<=l && n <= o;)
    /* this condition checks if all the first 'l' numbers of primes are found or n does not exceed the set limit o */
    {
            // this will divide n by prime number in p[j] and tries to rule out non-primes
            if ( n%p[j]==0 )
            {
                /* these steps execute if the number n is found to be non-prime */

                ++n; /* this increases n by 1 and therefore sets the next number 'n' to be tested */
                s=sqrt(n); /* this calaulates and stores in 's' the new root of number 'n' */
                if ( p[c] <= s && p[c] != x ) /* 'The Magic Setting' tests the next prime number candidate p[c] and if passed it updates the prime number x */
                {
                    x=p[c];
                    ++c;
                }
                j=1;
                /* these steps sets the next number n to be tested and finds the next prime number x if possible for the new number 'n' and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop for the new cycle */
            }
            // confirmation test for the prime number candidate n
            else if ( n%p[j]!=0 && p[j]==x )
            {
                /* these steps execute if the number is found to be prime */
                p[m]=n;
                printf("%10dth:%10d\n",m,p[m]);
                ++n;
                s = sqrt(n);
                ++m;
                j=1;
                /* these steps stores and prints the new prime number and moves the 'm' counter up and also sets the next number n to be tested and also resets j to 1 for the new cycle */
                continue; /* and this restarts the loop */
                /* the next number which will be a even and non-prime will trigger the magic setting in the next cycle and therfore we do not have to add another magic setting here*/
            }
            ++j; /* increases p[j] to next prime number in the array for the next cycle testing of the number 'n' */
            // if the cycle reaches this point that means the number 'n' was neither divisible by p[j] nor was it a prime number
            // and therfore it will test the same number 'n' again in the next cycle with a bigger prime number
    }
    // the loops ends
    printf("  All done !!\n");
    end = clock();
    cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC;
    printf("  Time taken : %lf sec\n",cpu_time_used);
}

这是我制作的代码：

enter code here
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT*/   

unsigned long int n;

int prime(unsigned long int);

scanf("%ld",&n);

unsigned long int val;

for(unsigned long int i=0;i<n;i++)
{
    int flag=0;

    scanf("%ld",&val);

    flag=prime(val);

    if(flag==1)
        printf("yes\n");

    else
        printf("no\n");
}

return 0;

}

int prime(unsigned long int n)
{

if(n==2) return 1;

else if (n == 1||n%2==0)  return 0;

for (unsigned long int i=3; i<=sqrt(n); i+=2)
    if (n%i == 0)
        return 0;

return 1;
}

在 Javascript 中使用 Array.prototype.find() 方法。2214.486 毫秒

function isPrime (number) {

  function prime(element) {
    let start = 2;
    while (start <= Math.sqrt(element)) {
      if (element % start++ < 1) {
        return false;
      }
    }
    return element > 1;
  }

  return [number].find(prime)

}

function logPrimes (n) {

  let count = 0
  let nth = n

  let i = 0
  while (count < nth) {
    if (isPrime(i)) {
      count++
      console.log('i', i) //NOTE: If this line is ommited time to find 10,000th prime is 121.157ms
      if (count === nth) {
        console.log('while i', i)
        console.log('count', count)
      }
    }
    i++
  }

}

console.time(logPrimes)

logPrimes(10000)

console.timeEnd(logPrimes) // 2214.486ms

我可以给你一些建议，你必须执行它。

对于每个数字，获取该数字的一半。例如。对于检查 21，只需将范围 2-10 相除即可获得余数。
如果是奇数，则只除以奇数，反之亦然。例如21，只能除以3、5、7、9。

迄今为止我所掌握的最有效的方法。

由于您只需要第一个10000个素数，而不是编码复杂算法，我会建议以下

boolean isPrime(int n){
//even but is prime
    if(n==2)
        return true;
//even numbers filtered already 
    if(n==0 || n==1 || n%2==0)
        return false;

// loop for checking only odd factors
// i*i <= n  (same as i<=sqrt(n), avoiding floating point calculations)
    for(int i=3 ; i*i <=n ; i+=2){
    // if any odd factor divides n then its not a prime!
        if(n%i==0)
            return false;
    }
// its prime now
    return true;
}

现在通话是您需要的首要任务

for(int i=1 ; i<=1000 ; i++){
    if(isPrime(i)){
       //do something
    }
}

using System;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, i = 3, j, c;
            Console.WriteLine("Please enter your integer: ");
            n = Convert.ToInt32(Console.ReadLine());
            if (n >= 1)
            {
                Console.WriteLine("First " + n + " Prime Numbers are");
                Console.WriteLine("2");
            }
            for(j=2;j<=n;)
            {
                for(c=2;c<=i-1;c++)
                {
                    if(i%c==0)
                        break;
                }
                    if(c==i)
                    {
                        Console.WriteLine(i);
                        j++;
                    }
                    i++;                                
            }
            Console.Read();
        }
    }
}

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow