获取Ada中的质数列表

Question

我编写了一个程序，用于在ADA中获取素数列表，并使用以下在线编译器:

https://rextester.com/l/ada_online_compiler

我的代码如下:

--GNAT 8.3.0
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO;

procedure prime is
function isPrime(n:in Integer) return Boolean is
begin
for i in 2..n loop
if n mod i=0 then 
return False;
end if;
end loop;
return True;
end isPrime;

begin
for i in 1..100 loop
if isPrime(i)=True then
Ada.Text_IO.Put_Line(Integer'Image(i));
end if;
Ada.Text_IO.Put_Line(Integer'Image(i));
end loop;
end prime;

而不是打印质数列表，它只打印1。我用C编写了相同的代码，完全没有问题。

Answer 1

isPrime()中的for循环检查大于1的每个值为"n mod n = 0"这将导致您对每个大于1的值返回false。将for循环条件更改为

for i in 2..(n-1) loop

并从那里开始工作

Answer 2

扩展Jere的方法，几个简单的素数检验将简化isPrime循环中的可除性检验:

• 唯一的偶素数2可以立即处理:

  if N = 2 then
  return True;
  end if;
  

• 所有剩余的偶数可以消除:

  if N mod 2 = 0 then
  return False;
  end if;
  

• 这在3 ..范围内留下奇数。√N检查:

  for i in 3 .. Positive (Sqrt (Float (N))) loop
  if N mod i = 0 then
  …
  end if;
  end loop;
  

Answer 3

定义一个包含素数的Prime_Number类型会更好。

subtype Prime_Number is Positive range 2 .. Positive'Last with
Dynamic_Predicate => (for all I in 2 .. (Prime_Number / 2) 
=> (Prime_Number mod I) /= 0);

然后，使用下面的代码段打印出2 ..之间的所有素数。100范围。

for Index in Positive range 2 .. 100 loop
if Index in Prime_Number then
Put_Line ("Prime number: " & Index'Image);
end if;
end loop;