求100以内素数的算法解决办法

求100以内素数的算法

Delphi(Pascal) code

procedure TForm1.a;var  X,Y : Integer;  i,j :Integer;  F : Boolean;begin  mmo1.Lines.Clear;  x:=0;  Y:=100;  if (x=0) or (x=1) or (x<0)  then  begin    X:=2  end;  for  i:=X to Y do  begin    F:=True;    for j:=2 to Trunc(Sqrt(i)) do  //  Trunc(Sqrt(i))  帮我解释下 为什么这里要平方根    begin      if (i mod j)=0  then      begin        F:=False;        Next;      end;    end;    if F then    begin      mmo1.Lines.Add(IntToStr(i));    end;  end;end;

[解决办法]
大于 平方根的 是 浪费，
[解决办法]
肯定 没有 合适的了
[解决办法]
举个很简单的例子你就明白了。

6

a. 6 / 1 = 6
b. 6 / 2 = 3
c. 6 / 3 = 2
d. 6 / 4 = 1.5
e. 6 / 5 = 1.2
f. 6 / 6 = 1

注意f项和a项，c项和b项事实上是等价的。
[解决办法]
假设要判断的整数是n，它的平方根是m

很显而易见的是，当整数n能被比它的平方根m还大的另一个整数p整除时，整除所得到的商q肯定是小于它的平方根m的。

而在判断n是否是素数的循环值(即p值)是由小到大依次进行的，上面情况中的小于m的q值肯定在循环的初期已经判断过了，所以大于m的整数值的判断是多余的。
[解决办法]
// Trunc(Sqrt(i)) 帮我解释下 为什么这里要平方根

 减少运算量而已,
假设A=B*C(设B<C) 
那么:
B<=Trunc(Sqrt(A)) 且 C>=Trunc(Sqrt(A)) 

[解决办法]
减少运算量而已
但是最好用古老的筛素数法
比这个要快指数倍
[解决办法]

探讨

// Trunc(Sqrt(i)) 帮我解释下 为什么这里要平方根

减少运算量而已,
假设A=B*C(设B<C)
那么:
B<=Trunc(Sqrt(A)) 且 C>=Trunc(Sqrt(A))

[解决办法]

探讨

减少运算量而已
但是最好用古老的筛素数法
比这个要快指数倍

查看更多 下一篇