中年熊资源吧:关于PASCAL的问题

程序如下：
方法一[基本方法]
program sushu(input,output);
var
i,j:integer;
f:boolean;
begin
for i:=100 to 200 do
begin
f:=true;
for j:=2 to i-1 do
if i mod j=0 then f:=false;
if f then writeln(i);
{打印出素数}
end;
end.
方法二[优化方法]
program sushu(input,output);
var
i,j:integer;
f:boolean;
begin
for i:=100 to 200 do
if i mod 2<>0 then begin
{优化，在100到200之间的偶数不可能是素数}
f:=true;
for j:=3 to trunc(sqrt(i)) do
{优化，前面已经判定了：偶数就不做，所以不必试2}
if i mod j=0 then f:=false;
if f then writeln(i);
{打印出素数}
end;
end.

这个。。
建议去网络上看看筛法的东西，比较有用。
其实只要求100-200，用for一个一个判断就可以了

应该学学集合。
这道题目如果为了初学者练习的话，最好用集合来写筛法。

记得以前Tongji Online Judge还开着的时候有这么一道题,我曾经搞了一个解题报告(不要BS哈)

一．问题描述
Problem
素数是的只能被1和它本身整除的自然数。判断一个数是素数的方法是使用2 到该数的平方根的素数除它，若有能整除的则该数不是素数。
Input
本题有多组数据，每组数据由两个正整数M,N组成。( 0＜M＜N＜1000000 )
Output
输出一个整数，表示介于M,N之间（包括M,N）的素数的数量。

二．问题的求解

1.错误分析：

一般来讲此题有两种做法：

即时判断一个数是否是素数，但速度显然太慢；

开一个数组来当素数表，这样就解决了速度问题，但空间的消耗又太大

问题既然出在这里，我们就要解决它！

2.对于此题，我一共想到了四种方法（其中之一基本上算cheat）

方法一：分段统计

方法解释：

在统计x到y的素数个数的过程中，假如存在i，j（x<i<j<y）,且在我们知道i到j的素数个数的情况下，x到y的素数个数即可以表达为：

X到（i-1）的素数个数+i到j的素数个数（已知）+（j+1）到y的素数个数

源代码：

program countnum;
var m,n,s,longint;
function pd(x:longint):boolean;
var i,d:integer;
begin
if x=1 then begin pd:=false;exit end;
d:=trunc(sqrt(x));
pd:=true;
for i:=2 to d do if x mod i=0 then begin pd:=false;exit end
end;
begin
while not seekeof do begin
read(m,n);
s:=0;
=0;
for s:=m to n do
begin
if (s<=2) and (n>99999) then begin s:=99999;inc(o,9592) end;
if (s=99999) and (n>500000) then begin s:=500000;inc(o,31946) end;
if (s=500000) and (n>700000) then begin s:=700000;inc(o,15005) end;
if (s=700000) and (n>900000) then begin s:=900000;inc(o,14731) end;
if pd(s) then inc(o)
end;
writeln(o)
end;
end.

方法二：空间压缩

方法解释：

其实一个Byte类型一共有八个二进制位，即它可以表达8个互不干扰的信息，那么假如我们能好好的利用这一点，那我们建的素数表就不再超空间了

源代码：

program countnum;

var a:array[1..125000]of byte; m,n,s,i:longint;
function tf(x:longint):boolean;
var b,c:longint;
begin
tf:=false;
b:=x mod 8; c:=(x div 8)+1; if b=0 then c:=c-1;
if (b=1)and((a[c] mod 2)>=1) then tf:=true;
if (b=2)and((a[c] mod 4)>=2) then tf:=true;
if (b=3)and((a[c] mod 8)>=4) then tf:=true;
if (b=4)and((a[c] mod 16)>=8) then tf:=true;
if (b=5)and((a[c] mod 32)>=16) then tf:=true;
if (b=6)and((a[c] mod 64)>=32) then tf:=true;
if (b=7)and((a[c] mod 128)>=64) then tf:=true;
if (b=0)and(a[c]>=128) then tf:=true;
end;
procedure make;
var d,e,f,g:longint;
begin
for i:=1 to 125000 do a[i]:=255;
a[1]:=254;
for d:=1 to 1000000 do
if tf(d) then
for e:= 2 to (1000000 div d) do
if tf(d*e) then
begin
g:=((d*e) div 8)+1; f:=(d*e) mod 8; if f=0 then g:=g-1;
if f=1 then a[g]:=a[g]-1
else if f=2 then a[g]:=a[g]-2
else if f=3 then a[g]:=a[g]-4
else if f=4 then a[g]:=a[g]-8
else if f=5 then a[g]:=a[g]-16
else if f=6 then a[g]:=a[g]-32
else if f=7 then a[g]:=a[g]-64
else if f=0 then a[g]:=a[g]-128;
end;
end;
begin
make;
while not eof(input) do
begin
s:=0;
readln(m,n);
for i:=m to n do
if tf(i) then s:=s+1;
writeln(s);
end;
end.

方法三：建一个真正的素数表（cheat）

方法解释：

素数太少了！空间太浪费了，所以一个BT的方法诞生了！

源代码：

program countnum;

const a:array[1..78499]of longint=({素数表});
var
n,m:longint;
function find(x:longint):longint;
var i:longint;
begin
for i:=1 to 78499 do
if x=>I then
begin
find:=i;
break;
end;
end;
begin
while not eof(input) do
begin
readln(n,m);
writeln(find(m)-find(n));
end;
end.

方法四：加速判断

方法解释：

我们可以先建一个1..1000的素数表，那么我们就可以利用这个小素数表来快速判断一个数是否是素数了（注意假如n是和数，那1..sqrt(n)中必定有n的因数）

源代码：

跟直接判断的方法大同小异，在这里我就不再浪费笔墨了！

其实方法主要就是这几个,而且本题比你所问的问题难度要高一点,所以.........

VAR A，I，J，K：INTEGER；
BEGIN
FOR I：=100 TO 200 DO
BEGIN
FOR J：=2 TO （I-1） DO
IF I MOD J = 0 THEN K：=1
IF K<>0 THEN WRITELN(I);
END;
END.

完整程序如上！