求100以内的所有素数

求100以内的所有素数什么是素数除0和1以外，只有1和它本身这两个因数的数是素数如235……第一种方法我们很容易找到1——10里面的素数2357o凡不是这4个数的倍数的数都为素数publicclassPrimeDemo{publicstaticvoidmainString[]args{primeNumber;}publicstaticvoidprimeNumber{intcount=4;StringBuildersb=newStringBuilder;sb.append2+〃〃+3+〃〃+5+〃〃+7+〃〃;forinti=10;i=100;i++{ifi%2==0||i%3=01|i%5==0||i%7==0{continue;}else{sb.appendi+/z〃；count++;System.out.printincount;System.out.printinsb.toStringO;}}第二种方法根据素数的定义只有1和它本身这两个因数的数称为素数可以理解为，一个数n只要不能被［2n-1］之间的数整除，那它就是一个素数以sqrt为分界点的原因首先，因数是成对出现的比如24你找到个约数3那么一定有个约数8因为24/3=8然后，这对约数必须一个在根号n之前，一个在根号n之后因为都在根号n之前的话，乘积一定小于n根号nX根号n=n同样，都在根号n之后的话，乘积一定大于n所以，如果你在根号n之前都找不到因数的话那么根号n之后就不会有了//primeNumber;primeNumber2;}〃根据素数的定义找素数publicstaticvoidprimeNumber{intcount=0;inti;intj;fori=2;i=100;i++{forj=2;j=i-l;j++{ifi%j==O{break;}}ifj=i{count++;Systemout.printi+/z〃;}}Systemout.printin;Systemout.printincount;}〃============================优化/*外层循环代表被除数由于1既不是质数也不是合数，所以从2开始内层循环代表除数*/publicstaticvoidprimeNumber2{intcount=0;StringBuildersb=newStringBuilder;forinti=2;i=100;i++{intj;intk=intMath.sqrti;forj=2;j=k;j++{ifi%j==O{break;}}ifjk{count++;sb.appendi+，/〃；}}Systemout.printincount;Systemout.printinsb.toStringO;}}第三种方法除2以外的所有偶数都不是素数，因此可以筛选一半元素，剩下的数都为奇数外层循环可筛选掉一半被除数奇数二奇数*奇数，它不可能被一个偶数整除内层循环可筛选掉一般除数publicstaticvoidisPrime{//2也为素数StringBuildersb=newStringBuiIder（，2）;intcount=1;〃记录素数的个数已经有2这个素数了，所以count的初始值为1forinti=3;i=100;i+=2{〃从3开始，以2为步长，限定每个被除数都是奇数intj;booleanflag=true;〃flag为true时，是素数；为false时，是和数forj=3;j〈i;j+=2{〃j从3开始，以2为步长，限定每个除数都是奇数因为一个奇数是不可能被一个偶数整除的ifi%j==O{〃如果i能够被j整除flag=false;}}ifflag{count++;sb.appendi+z/〃；}}Systemout.printincount;Systemout.printinsb.toStringO;}}第四种方法埃拉托斯特尼筛法:具体步骤.先将1删去因为1不是素数.用2去除它后面的各个数，把能被2整除的数删掉，即把2的倍数删掉.用3去除它后面的各数，把3的倍数删掉.分别用57…各数作为除数去除这些数以后的各数.一直到sqrti为止然后重复上述步骤上述操作需要一个很大的容器去装载所有数的集合，只要满足上述条件，即2的倍数大于1的全部置03的倍数大于1的全部置04的倍数大于1的全部置0……一直到这个数据集合的末尾，这样一来不为0的数就是素数了，然后按下标在里面进行查找publicstaticvoidisPrime{〃默认值为00——素数；1——合数〃这里写101是因为数组的下标是从0开始的，而要求的是1——100之间的素数int[]arr=newint

[101];〃01都不是素数，标记为1arr

[0]=1;arr

[1]=1;/**求1——100之间的素数，把2的倍数过滤掉，3的倍数过滤掉，5的倍数过滤掉，7的倍数过滤掉，一直到sqrt100的倍数过虑掉这*些都是2——sqrt100之间的素数的倍数**/forinti=0;i=Math.sqrt100;i++{ifarr[i]=0{//forintj=2*i;j=100;j+=i{〃可以从2*i修改成i*i因为在前面的循环中从2——i-1的倍数都已经验证过forintj=i*i;j=100;j+=i{arr[j]=l;}}}intcount=0;forintx=0;x=100;x++{ifarr[x]-0{count++;Systemout.printx+〃〃;}}Systemout.printlnO;System.out.printincount;}}欢迎大家给我建议，若诸位还有好的方法，欢迎一起交流。