07质数问题.pptx

质数问题求1~100000之间所有的质数，并统计质数的个数。分析：一个整数n，如果不能被2~n-1之间的任意整数整除，则这个数是质数i=2怎么跳出循环呢？在for，while，do..while循环体中，执行break语句，就能跳出循环，循环体内break后面的语句，不会被执行。如：for(int i=1;i10;i++){ if(i==5)break; couti‘ ‘;}falsei=100000truej=2falsej=i-1truefalsei%j!=0truej++falsej==i?true输出ii++结束#includeiostream#includectime //计算程序运行时间所需头文件using namespace std;const int N=100000;//加上const后，N成为常量，N必须在定义的时候初始化，且不能修改 int main(){ int count=0; for(int i=2;i=N;i++) { int j=2; while(j=i-1) { if(i%j==0)break; j++; } if(i==j){couti ;count++;} } coutendl质数个数：countendl; cout运行时间：((double)clock()/CLOCKS_PER_SEC)endl; //((double)clock()/CLOCKS_PER_SEC) 为程序运行时间，包括等待键盘输入的时间 return 0;}性能优化1：while(j=i-1i%j!=0)j++;实际上内层循环变量j，并不需要从2到i-1，只需要从2到i/2即可？性能优化2：?while(j=i/2i%j!=0)j++;实际上内层循环变量j，也不需要从2到i/2，只需要从2到即可？如果i不是质数，那么可以分解成两个整数a、b的乘积，即：i=a*b假设ab，那么a一定小于等于如果i有其它的约数，那么其中必定有小于等于的约数比如：36=2 X 18 (2 ) ，36=3 X 12 (3 )，36=4 X 9 (4= ) 36=6 X 6 (6=如果整数i，除1以外，没有小于等于的约数，那么i，除了它本身外，也不会有大于等 的约数，因此在判断i是否为质数时，j只需要从2到即可之前的方法需要对所有的数逐一判断12345679989991000…………质数集合111317……排除法思路：某一个数的倍数（自身除外）一定是合数 如 a = nXb(n!=1,b!=1,n为正整数)则a不是质数,排除a2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,…………49,50排除 2 的倍数2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39……49排除3的倍数2,3,5,7,11,13,17,19,23,25,29,31,35,37,41,43,45,47,49排除5的倍数2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,49最后在排除 7 的倍数，就可以得到50以内的质数排除法求质数假设2到100000，之间所有的数都是质数删除2的倍数，保留2删除3的倍数，保留3删除5的倍数，保留5…….i=2循环结束?i i是否已经被删除未被删除已被删除删除i的倍数，保留ii++下标标记法：怎么记录一个数是不是被删除呢？1.定义一个大小为100001的bool数组a。2.如果在1~100000中某一个数 i 没有被删除 ，记a[i]=0；如果删除啦，记a[i]=1；因此，数组a初始全都是0（0为false，非0为true）如果a[i]=0，表示i没被删除，a[i]=1，表示i被删除3.如果要将某一个数 t 删除，只要将a[t]赋值为1即可。请问：1.为什么a的大小不是100000，而是100001呢？ 2.处理完后，怎么判断一个整数x是否为质数呢？定义a[100001]，所有元素初始为0i=2j=2*i循环结束i ?j100000已被删除a[i]==0?a[j]=1;未被删除将a[2*i],a[3*i],a[4*i]…..通通赋值为1j+=ii++遍历数组a，如果a[i]等于0，则i是质数，输出i性能优化在删除 i 的倍数时，2*i，3*i，4*i，…..，(i-1)*i 已经被删除，所以没有必要重复操作，从i*i开始删除第一个删除的数是i*i，那么i不需要大于?2*i，3*i，4*i……(i-1)*i已经被删除定义a[100001]，所有元素初始为0i=2j=i*i循环结束i ?j100000已被删除a[i]==0?a[j]=1;未被删除将a[2*i],a[3*i],a[4*i]…..