自己想的一个算法。
求10亿以内质数的个数和总和。
program P6_15;
uses sysutils;{计时}
var i,j,k,m:longint;
t:int64;
time:real;
n:array[1..1000000000] of boolean;
begin
readln(i);{读取质数个数}
time:=now;
n[1]:=true;
for j:=1 to i do
begin
if n[j]=false then
begin
k:=k+1;
t:=t+j;
for m:=j to trunc(i/j) do
n[m*j]:=true;
end;
end;
writeln('sum=',t);
writeln('total=',k);
writeln('used time=',(now-time)*86400:5:3,'s');
readln;
end.
实际运行：
网上搜到一个”欧拉线性筛法“，时间复杂度是O(N),要怎么改进？

shy稍微来发表一些浅显的看法。
首先楼主这个筛法的复杂度是O(nloglogn)的。存在一种叫欧拉筛的筛法复杂度是O(n)的。不过实际上，由于欧拉筛也有常数，所以，两者实际运行时间貌似差别不大，欧筛仅仅略优（不过c++下差距还是有的，可能是pascal慢的缘故）。
我们看下运行结果感受下：
上面的是欧筛，10s多一些；下面的是楼主的普通筛，15s多一些。
当然，这个运行结果我已经对楼主筛法加一些常数优化。
楼主的代码如下：
{$OPTIMIZATION ON} //开启O2优化
{$R-,S-,Q-,I-} //关闭数组检查；关闭栈检查；关闭运算溢出检查；关闭输入检查；
//以上是Pascal的编译开关加速的一些简单技巧
program P6_15;
uses StructUnit; //shy曾发表的库，仅仅计时用
var tm:Timer;
var i,j,k,m:longint;
t:int64;
n:bitpacked array[1..1000000000] of boolean; //这里有个bitpacked用来压缩bool数组
//这里说明一下，bool本来存的信息是1位，但是不压位会以1字节存(8位)
//这样开的空间小了，索引、读取一定程度上会加快
begin
readln(i);{读取质数个数} //这个其实不是质数个数，是筛的范围
tm.Start; //开始计时
n[1]:=true;
for j:=1 to i do
begin
if n[j]=false then
begin
k:=k+1;
t:=t+j;
for m:=j to i div j do //实数除改成了div
n[m*j]:=true;
end;
end;
writeln('sum=',t);
writeln('total=',k);
writeln('used time=',tm.Time,'ms');
readln;
end.
综上讲这个程序还是常规的筛法，质数个数为n/ln(n)所以复杂度有保证O(nloglogn)，但是一个数可能被筛多次。而欧拉筛保证了一个数仅被筛1次。
欧拉筛代码：
{$OPTIMIZATION ON}
{$R-,Q-,S-,I-}
uses StructUnit;
var t:Timer;
var
n,i,j,k,pri:longint;
s:int64;
a:bitpacked array[0..1000000005]of boolean; //记录是否为质数
p:array[0..100000005]of longint; //记录质数
begin
read(n);
t.Start;
for i:=2 to n do
begin
if not a[i] then
begin
inc(pri);
p[pri]:=i;
inc(s,i)
end;
for j:=1 to pri do
begin
k:=i*p[j];
if k>n then break;
a[k]:=true;
if i mod p[j]=0 then break; //这里保证了每个数只被最小的质因子筛到，所以复杂度为O(n)
//当然实际上cpu中div 、mod运算比较慢，有些时候可以把a数组意义改作最小的质因子可以直接判，当然这样也是有常数的，所以速度差不多
end
end;
writeln('Sum = ',s);
write('Time = ',t.Time,'ms')
end.
欧拉筛在oi中算积性函数(比如φ，μ)等也很有用处，所以还是要好好了解一下的。
还有什么问题；或者讲错了；或者有更快的方法 欢迎回复。

打质数表复杂度O(1)