主题:help!!help!!
孤兰秋珊
[专家分:20] 发布于 2007-07-31 12:41:00
筛选法求素数!
输入n
输出N以内的所有素数!!(一定要是筛选法!)
回复列表 (共5个回复)
沙发
abcwuhang [专家分:1840] 发布于 2007-07-31 13:10:00
闷!
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.
板凳
Matodied [专家分:7560] 发布于 2007-07-31 13:20:00
筛选法求素数的方法是这样的:
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 楼
Matodied [专家分:7560] 发布于 2007-07-31 13:36:00
程序:
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 楼
abcwuhang [专家分:1840] 发布于 2007-07-31 14:51:00
...
5 楼
迷路的天使 [专家分:1340] 发布于 2007-11-20 19:20:00
不会 `~~~~~`
我来回复