求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))

------解决方案--------------------

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

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

相关推荐