先假设n是素数设立布尔型标志flag为true.pptVIP

Pascal常用算法 By阿默@2010.8 如何研究算法 算法是指解决问题的方法和步骤（≠代码！） 如何让基本算法成竹于胸？（不要背代码） 如何学习别人写的程序？（读程序打草稿） 多尝试思维训练而非写代码（草稿演算） 利用Fp调试功能来观察数据变化（F7+watch） 第一部分 数论算法 素数判定 最大公约数 最小公倍数 …… 素数判定 素数定义：除了1和本身之外，没有其它的约数。 思路：给出任意数N 分别用(2,sqrt(N))之间的整除去除N，如果N被任意一个整除就说明N不是素数，否则就是素数 大致算法 flag:=true; {先假设N是素数，设立布尔型标志flag为true } for i:=2 to trunc(sqrt(N)) do if N mod i=0 then {如果N被i整除} begin flag:=false; {N的标志量置为false，表明N不是素数} break; {可以立即跳出循环，不需要再循环了} end; writeln(flag); {输出标志量flag} 判断素数算法 将其设计成一个函数模块 function isprime(x:longint):boolean; var i:longint; flag:boolean; begin flag:=true; for i:=2 to trunc(sqrt(x)) do if x mod i=0 then begin flag:=false; break; end; isprime:=flag; end; 引 在纸上写一行数字，从2到24 ①将2的倍数划去，②将3的倍数划去。（都不划本身）。 你发现了什么？ 恭喜你！你已经找出了24以内的所有素数。 问：如果要找出100以内所有的素数，划几次？ 筛法策略求某个区间的所有素数 var a:array[2..1000000] of boolean; n,i,j:longint; begin readln(n); fillchar(a,sizeof(a),true); for i:=2 to trunc(sqrt(n)) do if a[i] then for j:=2 to n div i do a[i*j]:=false; for i:=2 to n do if a[i] then write(i, ); end. 筛法是一个策略 筛法不是一个具体的算法，而是一个策略，筛法最大的优点就是时间！在1s内求出2~N之间的素数时，用试除法的话N≥10万之后基本就超时了，而用筛法N最大可以大到一千万左右。 当然，没有绝对的优势，筛法的劣势就在于需要用到大量的空间，本来筛法就是一个用空间换取时间的策略。 请估算N时候采用筛法求素数是否会超过市赛中程序规定的内存空间？（布尔型按1字节计算。） 筛法策略其它典型问题 约数研究（common.pas） 小联最近在研究和约数有关的问题，每个正整数N（2≤N≤5000000）至少有两个约数，最小的一个是1，但小联并不关心它，因为所有正整数最小约数都是1。小联关心是正整数的第二小约数，并f(N)来表示，下表给出了一些f(N)的取值： N　　 2 3 4 5 f(N) 2 3 2 5 现在小联需要统计f(2) 到f(N)的累加和M。 样例输入：5 样例输出：12 换种思路，精简一下 function gcd(x,y:longint):longint; begin if x mod y=0 then gcd:=y else gcd:=gcd(y,x mod y); end; 换种思路，换种算法？ 有a，b两数，设c=min{a,b} ，然后利用从c至1逐个去试除 a ，b两数，一旦通过试除立即退出即得解。 最小公倍数算法 利用最大公约数 function lcm(x,y:longint):longint; begin lcm:= x * y div gcd(x,y); end; 还有别的算法吗？ 大数作翻倍运算。 第二部分 深入排序 选择排序 冒泡排序 插入排序 计数排序 多路排序※ 选择排序 多路排序 多路排序是信息学奥赛初学者必须掌握的内容之一，其大意是按照某一关键字进