前n素数的埃拉托色尼筛

Question

我正在尝试让我的埃拉托斯特尼筛程序仅输出用户请求的前n个素数。Sieve本身工作得很好 - 它正确地输出了前100个素数（如下面的数组所示），但是最后一个循环中的计数器变量无法正常工作，我无法找出原因。例如，如果用户输入“5”表示 n，则只会打印前 3 个定焦值。

有人可以帮我找出我的错误吗？我的目的是让“count”成为一个非常简单的计数器，每次都会增加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

我有一个使用Ada的解决方案，可能会给你一些帮助。我创建了一个名为Is_Prime的函数，当传递给它的参数是质数时返回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

Answer 2

你应该只计算质数，而不是所有的数。

此外，应更正循环的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
    }
}