前 n 个素数的埃拉托色尼筛法

Question

我正在尝试让我的埃拉托色尼筛法程序仅输出用户请求的前 n 个质数。 Sieve 本身工作得很好——它正确地输出前 100 个素数（如下面的数组），但最后一个循环中的计数器变量工作不正常，我不明白为什么。例如，如果用户为 n 输入“5”，则只会打印前 3 个素数。

有人可以帮我找出我的错误吗？我的意图是让“计数”成为一个非常简单的计数器，每次递增 1，直到达到 n。

int n;
cout << "Enter the number of primes you want to print:\n";
cin >> n;

int arr[100] {0};

for (int i = 2; i <= sqrt(100); i++)
{
    if (arr[i] == 0)
    {
        for (int j = 2; i*j<100; j++)
            arr[j*i] = 1;
    }
}

for (int i = 3, count = 0; i <= 100 && count != n; i++, count++)
{
    if (arr[i] == 0)
        cout << i << '\n';
}

Answer 1

您应该只计算素数，而不是所有数字。

循环的 i 范围也应该更正。第一个质数是2，元素arr[100]不可用。

for (int i = 2, count = 0; i < 100 && count != n; i++) // don't increment count here
{
    if (arr[i] == 0)
    {
        cout << i << '\n';
        count++; // count a prime number here
    }
}

Answer 2

我有一个使用 Ada 的解决方案，它可能会给你一些帮助。我创建了一个名为 Is_Prime 的函数，当传递给它的参数是质数时，returns 为 TRUE，否则为 FALSE。

以下是包含 Is_Prime 声明的包规范。将包规范视为类似于 C 头文件。

package Primality is
   function Is_Prime(Num : Positive) return Boolean;
end Primality;

函数的实现在包体中，大致对应一个C.c文件

-----------------------------------------------------------------------
-- Primality Body                                                    --
-----------------------------------------------------------------------
with Ada.Numerics.Generic_Elementary_Functions;

package body Primality is
   function Is_Prime (Num : Positive) return Boolean is
      package Flt_Funcs is new Ada.Numerics.Generic_Elementary_Functions
        (Float);
      use Flt_Funcs;

      T      : Integer          := 2;
      Limit  : constant Integer := Integer (Sqrt (Float (Num)));
      Result : Boolean          := True;
   begin
      if Num = 2 then
         Result := True;
      else
         while T <= Limit loop
            if Num mod T = 0 then
               Result := False;
               exit;
            end if;
            T := T + (if T > 2 then 2 else 1);
         end loop;
      end if;
      return Result;
   end Is_Prime;
end Primality;

Ada 允许程序员随意命名“主”文件。以下是允许用户指定要输出的素数的“主”文件。

with primality; use primality;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;


procedure List_Primes is
   count : Natural;
   Num   : Positive := 2;
begin
   Put("Enter the number of primes you want to print: ");
   Get(count);
   while count > 0 loop
      if Is_Prime(Num) then
         Put_Line(Num'Image);
         count := count - 1;
      end if;
      Num := Num + (if Num = 2 then 1 else 2);
   end loop;
end List_Primes;

样本运行的输出是：

Enter the number of primes you want to print: 20
 2
 3
 5
 7
 11
 13
 17
 19
 23
 29
 31
 37
 41
 43
 47
 53
 59
 61
 67
 71

前 n 个素数的埃拉托色尼筛法

Sieve of Eratosthenes for first n prime numbers

c++

sieve-of-eratosthenes