回 帖 发 新 帖 刷新版面

主题:help!!help!!

筛选法求素数!
输入n
输出N以内的所有素数!!(一定要是筛选法!)

回复列表 (共5个回复)

沙发

闷!
program shaixuan;
var a:array [1..10000] of boolean;
    i,j,n:longint;
begin
  fillchar(a,sizeof(a),true);
  a[1]:=false;
  for i:=2 to trunc(sqrt(n)) do
  begin
    j:=2;
    while i*j<=n do
    begin
      a[i*j]:=false;
      j:=j+1;
    end;
  end;
  for i:=1 to n do
    if a[i] then write(i,' ');
end.

板凳

筛选法求素数的方法是这样的:

1、在桌子上放上写有1-N之间的所有数的卡片。
2、扔掉1。
3、选择下一个没有被扔掉的数M,把M的倍数全部扔掉(M本身不扔掉)。
4、如果此次操作后,没有一个数被扔掉,那么桌子上还没被扔掉的数就是素数。

比如:(N=15)
1、在桌子上放上写有1-15之间的所有数的卡片。
2、扔掉1。
3、下一个没有被扔掉的数是2,把2的倍数4、6、8、10、12、14都扔掉。
   继续判断,下一个没有被扔掉的数是3,把3的倍数9、15扔掉。
   继续判断,下一个没有被扔掉的数是5,但是桌子上已经没有5的倍数(除了5本身)了,那么还没被扔掉的数2、3、5、7、11、13就是素数。

3 楼

程序:
TYPE arr = ARRAY[1..8191] OF BOOLEAN;
VAR
   a: arr;
   i, m, n, s, t: INTEGER; f: BOOLEAN;
BEGIN
    READLN(n);
    FOR i:=1 TO n DO a[i] := TRUE;
    a[1] := FALSE;
    m := 1; f := TRUE;
    REPEAT
         REPEAT
              INC(m);
         UNTIL a[m];
         s := m * 2; t := 0;
         IF s <= n THEN BEGIN
            REPEAT
                 a[s] := FALSE; t := t + 1;
                 s := s + m;
            UNTIL s > n;
         END;
         IF t = 0 THEN f := FALSE;
    UNTIL NOT f;
    FOR i:=1 TO n DO BEGIN
        IF a[i] THEN WRITE(i, ' ');
    END;
END.

4 楼

...

5 楼

不会  `~~~~~`

我来回复

您尚未登录,请登录后再回复。点此登录或注册