求100以内的所有素数.docx

《求100以内的所有素数.docx》由会员分享，可在线阅读，更多相关《求100以内的所有素数.docx（7页珍藏版）》请在第一文库网上搜索。

1、求IOO以内的所有素数什么是素数?除。和1以外，只有1和它本身这两个因数的数是素数。如2,3,5,第一种方法：我们很容易找到110里面的素数：2,3,5,7o凡不是这4个数的倍数的数都为素数。pub1icc1assPrimeDemopub1icstaticvoidmain(Stringargs)primeNumber();)pub1icstaticvoidprimeNumber()intcount=4;StringBui1dersb-newStringBui1derO;sb.append(2+3+5+7+)；for(inti=10;i=100;i+)if(i%2=0i%3=0i%5=0i%7=

2、0)continue;e1sesb.append(i+zz)；count+;System,out.printin(count);System,out.print1n(sb.toString();)第二种方法：根据素数的定义：只有1和它本身这两个因数的数称为素数。可以理解为，一个数(n),只要不能被2,(n-1)之间的数整除，那它就是一个素数。以Sqrt为分界点的原因：首先，因数是成对出现的。比如24,你找到个约数3,那么一定有个约数8,因为24/3=8。然后，这对约数必须一个在根号n之前，一个在根号n之后。因为都在根号n之前的话，乘积一定小于n(根号nX根号n=n)。同样，都在根号n之后的话，

3、乘积一定大于n。所以，如果你在根号n之前都找不到因数的话,那么根号n之后就不会有了。/ZprimeNumberO;primeNumber2();根据素数的定义找素数pub1icstaticvoidprimeNumber()intcount=O;inti;intj;for(i=2;i=100;i+)for(j=2;j=i)count+;System,out.print(i+,z);)System,out.print1n();System,out.printin(count);=优化* 外层循环代表被除数。由于1既不是质数也不是合数，所以从2开始* 内层循环代表除数。* */pub1icstati

4、cvoidprimeNumber2()intcount=0;StringBui1dersb-newStringBui1derO;for(inti=2;i=100;i+)intj;intk=(int)Math.sqrt(i);for(j=2;jk)count+;sb.append(iz,)；System,out.printin(count);System,out.printin(sb.toString();)第三种方法：除2以外的所有偶数都不是素数，因此可以筛选一半元素，剩下的数都为奇数。外层循环可筛选掉一半被除数。奇数二奇数*奇数，它不可能被一个偶数整除。内层循环可筛选掉一般除数。pub1ic

5、staticvoidisPrime()2也为素数StringBuiIderSb=newStringBui1der(z,2)；intcount=1;记录素数的个数。已经有2这个素数了，所以CoUnt的初始值为1for(inti=3;i=100;i+=2)从3开始,以2为步长，限定每个被除数都是奇数intj;boo1eanf1ag=truc;f1ag为true时,是素数;为fa1se时,是和数for(j=3;ji;j+=2)j从3开始，以2为步长，限定每个除数都是奇数。因为一个奇数是不可能被一个偶数整除的if(i%j=O)如果i能够被j整除f1ag=fa1se;)if(f1ag)count+;sb

6、.append(i+zz)；)System,out.printin(count);System,out.print1n(sb.toString();)第四种方法(埃拉托斯特尼筛法)：具体步骤：1 .先将1删去(因为1不是素数)。2 .用2去除它后面的各个数，把能被2整除的数删掉，即把2的倍数删掉。3 .用3去除它后面的各数，把3的倍数删掉。4 .分别用5,7各数作为除数去除这些数以后的各数。5 .一直到Sqrt(i)为止。然后重复上述步骤。上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的倍数大于1的全部置0,3的倍数大于1的全部置0,4的倍数大于1的全部置0一直到这个数据

7、集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找。pub1icstaticvoidisPrime()默认值为0,0素数；1合数这里写101是因为数组的下标是从0开始的，而要求的是1100之间的素数intarr=newint101;0,1都不是素数，标记为1arr0=1;arr1=1;/*求1100之间的素数，把2的倍数过滤掉，3的倍数过滤掉，5的倍数过滤掉，7的倍数过滤掉，一直到Sqrt(IOo)的倍数过虑掉(这*些都是2Sqrt(IOO)之间的素数的倍数)*/for(inti=0;i=Math.sqrt(100);i+)if(arri=0)/for(intj=2*i;j=100;j+=i)可以从2*i修改成i*i,因为在前面的循环中从2(A1)的倍数都已经验证过for(intj=i*i;j=100;j+=i)arrj=1;)intcount=0;for(intx=0;x=100;x+)if(arrx=0)count+;System,out.print(x+z,)；)System,out.print1n();System,out.printin(count);欢迎大家给我建议，若诸位还有好的方法，欢迎一起交流。