如何在Delphi中检查素数

Question

我想将1到10000之间的所有素数读入动态数组,将所有非素数读入另一个动态数组,然后读取素数数组richedit1到目前为止我有:

procedure primearrays;
var
  j, k, l, i, m: integer; // k is the number I am testing for prime number
  // j is used in the for loop to check all numbers smaller than k to see if k is dividable by j
  // l is just a variable set to k mod j to make the if run more smoothly
  // i is the length of the array anotprime
  // m is used to set the length of the array aprime
  bflag: boolean; // bflag is to show if this number is a prime number
  aprime, anotprime: array of integer;
  // aprime is the array of prime and anotprime is the array of nonprime numbers
begin
  j := 0;
  i := 0;
  l := 0;
  richedit1.Lines.Clear;
  bflag := false;
  for k := 2 to 10000 do
  begin
    j := 0;
    while not(j = (k - 1)) do
    begin
      inc(j);
      l := k mod j;
      if (l = 0) then
      begin
        bflag := false;
        inc(i);
        setlength(anotprime, i);
        anotprime[i - 1] := k;
        j := k - 1;
      end
      else
      begin
        bflag := true;
      end;
    end;
    m := -1;
    if (bflag) then
    begin
      inc(m);
      setlength(aprime, m);
      aprime[m - 1] := k;
      richedit1.Lines.Add(inttostr(aprime[l-1]));
    end;
  end;
end;

但这似乎不起作用.它将所有整数放入anotprime.

Answer 1

也许你遇到的主要问题是你将所有不同的方面(循环候选,素数检查,显示等)混合到一个函数中.

如果将任务分解为仅执行单个任务的小块,生活将变得更加容易.从函数开始测试数字是否为素数.

function IsPrime(N: Integer): Boolean;
var
  M: Integer;
begin
  Assert(N > 0);
  if N = 1 then // annoying special case
  begin
    Result := False;
    exit;
  end;
  for M := 2 to (N div 2) do
    if N mod M = 0 then
    begin
      Result := False;
      exit;
    end;
  end;
  Result := True;
end;

现在您可能希望创建一个包含素数的列表:

var 
  Primes: TList<Integer>;
  N: Integer;
....
// create Primes
for N := 1 to 10000 do
  if IsPrime(N) then
    Primes.Add(N);

这不是枚举素数的最有效方法.但它可能就是你应该从哪里开始的,我主要是写这个答案,鼓励你将代码分成很小的逻辑方法来完成特定的重点任务.