求100以内的所有素数.docx

《求100以内的所有素数.docx》由会员分享，可在线阅读，更多相关《求100以内的所有素数.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、求100以内的所有素数什么是素数?除0和1以外，只有1和它本身这两个因数的数是素数。如2, 3, 5,第一种方法：我们很容易找到110里面的素数：2, 3, 5, 7o凡不是这4个数的倍数 的数都为素数。public class PrimeDemo public static void main(String args) primeNumber();public static void primeNumber()int count =4;StringBuilder sb =new StringBuilder();sb. append(2+3+5+7+ );for(int i=10;i=100;

2、i+)if(i%2=0| | i%3=01 | i%5=0| | i%7=0) continue;else sb. append (i+/z )； count+;System. out. printin(count);System. out. printin (sb. toStringO);第二种方法：根据素数的定义：只有1和它本身这两个因数的数称为素数。可以理解为，一个 数(n),只要不能被2, (n-1)之间的数整除，那它就是一个素数。以sqrt为分界点的原因：首先，因数是成对出现的。比如24,你找到个约数3,那么一定有个约数8, 因为24/3=8。然后，这对约数必须一个在根号n之前，一个

3、在根号n之后。因 为都在根号n之前的话，乘积一定小于n (根号nX根号n=n)。同样，都在根号 n之后的话，乘积一定大于n。所以，如果你在根号n之前都找不 到因数的话, 那么根号n之后就不会有了。/primeNumber ();primeNumber2 ();根据素数的定义找素数public static void primeNumber() int count =0;int i;int j;for(i =2;i=100;i+)for (j =2;j=i)count+;System, out. print (i+/z );System, out. printin ();System, out.

4、 printin(count);=优化/* 外层循环代表被除数。由于1既不是质数也不是合数，所以从2开始* 内层循环代表除数。* */public static void primeNumber2()int count =0;StringBuilder sb =new StringBuilder();for(int i=2;i=100;i+) int j; int k =(int)Math. sqrt(i);for(j=2;jk)count+;sb. append (i+，/ )；System, out. printin(count);System, out. printin (sb. toS

5、tringO);第三种方法：除2以外的所有偶数都不是素数，因此可以筛选一半元素，剩下的数都为奇 数。外层循环可筛选掉一半被除数。奇数二奇数*奇数，它不可能被一个偶数整除。内层循环可筛选掉一般除数。public static void isPrime()/2也为素数StringBuilder sb =new StringBuiIder （,，2 ）;int count=1;记录素数的个数。已经有2这个素数了，所以count的初始值 为1for(int i=3;i=100;i+=2) 从3开始，以2为步长，限定每个被除数都是奇 数int j;boolean flag =true;flag 为 tr

6、ue 时，是素数；为 false 时，是和数for(j=3;ji;j+=2)j从3开始，以2为步长，限定每个除数都是奇数。因为一个奇数是不可能被一个偶数整除的if(i%j=O) 如果i能够被j整除flag =false;if (flag) count+;sb. append (i+z/ )；System, out. printin (count);System, out. printin (sb. toStringO);第四种方法(埃拉托斯特尼筛法):具体步骤：1 .先将1删去(因为1不是素数)。2 .用2去除它后面的各个数，把能被2整除的数删掉，即把2的倍数删掉。3 .用3去除它后面的各数，

7、把3的倍数删掉。4 .分别用5, 7各数作为除数去除这些数以后的各数。5 . 一直到sqrt(i)为止。然后重复上述步骤。上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即 2的倍数大于1的全部置0, 3的倍数大于1的全部置0, 4的倍数大于1的全部 置0一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按 下标在里面进行查找。public static void isPrime()默认值为0, 0素数；1 合数这里写101是因为数组的下标是从0开始的，而要求的是1100之间的素 数int arr =new int101;0, 1都不是素数，标记为1arr0=1;ar

8、r1=1;/*求1100之间的素数，把2的倍数过滤掉，3的倍数过滤掉，5的倍数过滤 掉，7的倍数过滤掉，一直到sqrt (100)的倍数过虑掉(这*些都是2sqrt (100)之间的素数的倍数)* */for(int i =0;i=Math. sqrt(100);i+) if (arri=0) /for(int j=2*i;j=100;j+=i)可以从2*i修改成i*i,因为在前面的循环中从2(i-1)的倍数都已经验证 过for(int j=i*i;j=100;j+=i)arrj=l;int count=0;for(int x =0;x=100;x+)if (arrx-0) count+;System, out. print (x+ );System, out. printlnO ;System. out. printin(count);欢迎大家给我建议，若诸位还有好的方法，欢迎一起交流。