UC知道PASCAL 开辟变量 耗时
来源：百度知道 编辑：UC知道 时间：2024/06/06 00:34:01
要参加NOIP复赛了
今天本人电脑上看到一道题，求1-1亿中的超级素数，本人计算了一下，光是为了求1-1亿中的素数开辟一个【1..100000000】OF BOOLEAN的变量（大概11M）就花了10秒....
请问PASCAL中开辟变量的耗时和机器有关系吗？
一般开辟变量都要花多少时间？
如果你足够高手的话，面对如此长的耗时，你会这么做这题？（只有2秒）
超级素数（SUPER PRIME）
提交文件名：SPRIME.PAS
问题描述：
如果一个自然数其本身就是一个素数，而且从这个数的右边每次去掉一个数字，余下的数仍然保持为素数，直到最后一位为止，则这个数称其为超级素数。例如：7331。
7331为素数，733为素数，73为素数，7也为素数，则7331为超级素数。
问题求解：
编写一个程序，打印输出1亿以内的所有超级素数，每行八个，每个场宽为10，以及超级素数总的个数。
（总运行时间不得超过2秒）。
参考：找出1亿以内所有的素数。 【我不是用这个程序算素数的】
var
i,j : longint;
b : boolean;
begin
for i := 1 to 100000000 do begin
b := true;
for j := 2 to i div 2 do
if i mod j = 0 then b := false;
if b then write(i,#9);
end;
readln;
end.
今天本人电脑上看到一道题，求1-1亿中的超级素数，本人计算了一下，光是为了求1-1亿中的素数开辟一个【1..100000000】OF BOOLEAN的变量（大概11M）就花了10秒....
请问PASCAL中开辟变量的耗时和机器有关系吗？
一般开辟变量都要花多少时间？
如果你足够高手的话，面对如此长的耗时，你会这么做这题？（只有2秒）
超级素数（SUPER PRIME）
提交文件名：SPRIME.PAS
问题描述：
如果一个自然数其本身就是一个素数，而且从这个数的右边每次去掉一个数字，余下的数仍然保持为素数，直到最后一位为止，则这个数称其为超级素数。例如：7331。
7331为素数，733为素数，73为素数，7也为素数，则7331为超级素数。
问题求解：
编写一个程序，打印输出1亿以内的所有超级素数，每行八个，每个场宽为10，以及超级素数总的个数。
（总运行时间不得超过2秒）。
参考：找出1亿以内所有的素数。 【我不是用这个程序算素数的】
var
i,j : longint;
b : boolean;
begin
for i := 1 to 100000000 do begin
b := true;
for j := 2 to i div 2 do
if i mod j = 0 then b := false;
if b then write(i,#9);
end;
readln;
end.
这道题必然不能这么做..数组需要初始化的..初始化的时间 就是 数组的大小除以 10^8(普遍这么认为...)
所以你那样做数据再大点你这辈子也做不出来了..
应该是先筛出来第一个是素数的，然后在此基础上筛第二位..以此类推...直到满足条件为止
话说这道题貌似是USACO上面的....
用递归
program ex01;
var
a,b,x,i:longint;
function pz(x:longint):boolean;
var
i:longint;
begin
if ((x=0) or (x=1)) then pz:=false
else if ((x=2) or (x=3)) then pz:=true
else begin
for i:=2 to trunc(sqrt(x)) do
if pz(i) then if x mod i=0 then begin pz:=false;exit;end;
pz:=true;
end;
end;
begin
readln(a);
for i:=1to a do
if pz(i) then begin writeln(i:10);x:=x+1;end;
writeln(x);
end.
这个速度与虚拟内存有关
应该用hash表来做
在USACO上做过，比较简单