A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 blensmile 于 2015-10-4 20:33 编辑

  1. class prime {

  2.         static void prt(String s){
  3.                 System.out.print(s);
  4.         }
  5. /*
  6. 基本思想:
  7. 1.合数都可以彻底分解为质数与质数的乘积,即合数总是可以找到至少一个质数使得这个合数%素数==0
  8. 2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有素数),如果没有一个能除尽,则x是素数
  9. 3.任何合数成对的因数中,必然有一个小于等于这个数开方的根,例如sqrt(12)=3.4,12=2*6=3*4,2和3都小于3.4
  10.   所以只需要比较到sqrt(x)就可以确定这个数是不是素数了

  11. 基于以上思想,创建一个数组由小到大存储已经确认的素数,即存储,也用来运算,代价是要使用比较多的内存
  12. */
  13.         private static void primeTest1(int a){
  14.                 int i = 0;
  15.                 int j = 0;
  16.                 int sqrtNum = 0;
  17.                 int arryNum = (int)(a*1.2/Math.log((double)a));
  18.                 int prim[] = new int[arryNum];        //创建一个数组
  19.                 for(i = 0;i<arryNum;i++)                                
  20.                         prim[i] = i+2;                             //数组初始化,prim[0] = 2...
  21.                 int countNum = 2;                            //已经有2,3 这2个素数
  22.                 long startTime=System.currentTimeMillis();//用于计时
  23.                 for(i=5;i<a;i+=2){                               //从5开始,步长为2,直接排除偶数参与运算
  24.                         sqrtNum = (int)Math.sqrt(i);      //计算i开方的值,转换为int型
  25.                         for(j=1;j<=countNum;j++){       //prim[0]=2,prim[1]=3,已排除偶数,故从3开始参与运算,
  26.                                 if((i%(prim[j]))==0)             //i被prim中存储的素数除尽,证明它不是素数,跳出循环
  27.                                         break;
  28.                                 if( prim[j] > sqrtNum ){       //除数的素数值已经大于被除数的开方值,判断这个数是素数
  29.                                         prim[countNum] = i;    //存储
  30.                                         countNum++;              //
  31.                                         break;                           //完成质数的确认,跳出循环
  32.                                 }
  33.                         }
  34.                 }

  35.                 System.out.println("\nTest1 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
  36.                 i = 0;
  37.                 System.out.println("countNum : " + countNum);   //打印素数总数
  38. //                while(i<count){               //打印每个素数
  39. //                        System.out.print(prim[i]+"\t");                                       
  40. //                        i++;
  41. //                }
  42.         }
  43. /*
  44. 基本思想:
  45. 1.所有素数一定是奇数,因为偶数可以被2整除
  46. 2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有奇数),如果没有一个能除尽,则x是素数
  47. 3.任何合数成对的因数中,必然有一个小于等于这个数开方的根,例如sqrt(12)=3.4,12=2*6=3*4,2和3都小于3.4
  48.   所以只需要比较到sqrt(x)就可以确定这个数是不是素数了
  49. */
  50.         private static void primeTest2(int a){
  51.                 int i;
  52.                 int j;
  53.                 int countNum = 2;
  54.                 int sqrtNum =0;
  55. //                System.out.print("2\t3\t");   //需要输出解除注释,
  56.                 long startTime=System.currentTimeMillis();
  57.                 for( i = 5;i<a;i+=2){         //从5开始,步长为2,直接排除偶数参与运算
  58.                         sqrtNum = (int)Math.sqrt(i);
  59.                         for(j = 3;j<i;j+=2){
  60.                                 if(i%j ==0)
  61.                                         break;
  62.                                 if(j > sqrtNum){
  63.                                         countNum++;
  64. //                                        System.out.print(i + "\t");   //需要输出解除注释,
  65.                                         break;
  66.                                 }
  67.                         }
  68.                 }
  69.                 System.out.println("\nTest2 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
  70.                 System.out.println("countNum : " + countNum);
  71.         }

  72. /*
  73. 基本思想:
  74. 1.所有素数一定是奇数,因为偶数可以被2整除
  75. 2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有奇数),如果没有一个能除尽,则x是素数
  76. */
  77.         private static void primeTest3(int a){
  78.                 int i;
  79.                 int j;
  80.                 int countNum = 2;
  81. //                System.out.print("2\t3\t");   //需要输出解除注释,
  82.                 long startTime=System.currentTimeMillis();
  83.                 for( i = 5;i<a;i+=2){                //从5开始,步长为2,直接排除偶数参与运算
  84.                         for(j = 3;j<i;j+=2){
  85.                                 if(i%j ==0)
  86.                                         break;
  87.                                 if(j+2 == i){
  88.                                         countNum++;
  89. //                                        System.out.print(i + "\t");    //需要输出解除注释,
  90.                                         break;
  91.                                 }
  92.                         }
  93.                 }
  94.                 System.out.println("\nTest3 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
  95.                 System.out.println("countNum : " + countNum);
  96.         }

  97. /*
  98. 基本思想:
  99. 拿到任意一个在取值范围以内的数字x,用x%(比x小的所有数),如果没有一个能除尽,则x是素数
  100. */
  101.         private static void primeTest4(int a){
  102.                 int i;
  103.                 int j;
  104.                 int countNum = 1;                        //此时默认2是素数
  105. //                System.out.print("2\t");
  106.                 long startTime=System.currentTimeMillis();
  107.                 for( i = 3;i<a;i++){        //从3开始,因为2%2==0,会影响判断
  108.                         for(j = 2;j<i;j++){
  109.                                 if(i%j ==0)                                
  110.                                         break;
  111.                                 if(j+1 == i){    //判断到比i小1,这时可以确认它是素数
  112.                                         countNum++;
  113. //                                        System.out.print(i + "\t"); //需要输出解除注释,
  114.                                         break;
  115.                                 }
  116.                         }
  117.                 }
  118.                 System.out.println("\nTest4 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
  119.                 System.out.println("countNum : " + countNum);
  120.         }

  121. /*


  122. */
  123.         public static void main(String args[]) {
  124.                
  125.                 int maxNum = 300000;        //通过这里设置取值上限,完成4种方法运行时间的实验
  126.                 prt("Hello Cruel World!\n");
  127.                 primeTest1(maxNum);
  128.                 primeTest2(maxNum);
  129.                 primeTest3(maxNum);
  130.                 primeTest4(maxNum);
  131.         }

  132. }
复制代码

17 个回复

倒序浏览
这个方法太麻烦了吧。。
回复 使用道具 举报
  1. class Hello{
  2.         public static void main(String[] args){
  3.         int sum = 0;
  4.                 for (int i = 1; i <= 100; i++){
  5.                         int count = 0;
  6.                         for (int j = 1;j <= i;j++){
  7.                                 if(i % j == 0){
  8.                                         count ++;
  9.                                 }
  10.                         }
  11.                         if (count <= 2){
  12.                                 System.out.println(i);
  13.                                 sum ++;
  14.                         }
  15.                 }
  16.                 System.out.println("total:"+sum);
  17.         }
  18. }
复制代码
回复 使用道具 举报

把100换成10000即可。
素数,也就是只能被1或者他本身整除。
换句话说,只要看一个数能被除了1和他本身两个数之外有没有可以整除的数就好了。
count为计数器,如果计数器大于2,则不是素数,不打印。
回复 使用道具 举报

你这是最最基础的方法,代码复杂度低,但是时间复杂度太高了,数一大,运算量就急剧增长。
回复 使用道具 举报
感谢楼主提供的思路,认真学习一下!
回复 使用道具 举报
看不懂 学一下        
回复 使用道具 举报
虽然有点复杂,但是感觉很有想法的样子
回复 使用道具 举报
  1. public class Test {  
  2.   
  3.     private static boolean prime[] = new boolean[10001];  
  4.   
  5.     // 线性素数筛选法  
  6.     static {  
  7.         prime[0] = true;  
  8.         prime[1] = true;  
  9.         for (int i = 2; i < 101; i++) {  
  10.                         //如果是false,说明有可能是素数,那么素数的倍数就不是素数,将该数字的倍数都标记为true
  11.             if (!prime[i]) {  
  12.                 for (int j = i * i; j < prime.length; j += i)  
  13.                     prime[j] = true;  
  14.             }  
  15.         }  
  16.     }  
  17.   
  18.     public static void main(String[] args) {  
  19.   
  20.                 // 打印素数
  21.                 int j = 0;
  22.         for(int i = 2; i < prime.length; i++)
  23.                 {
  24.                         if(!prime[i])
  25.                         {
  26.                                 j++;
  27.                                 System.out.print(i+" ");
  28.                         }
  29.                         if(j == 10)
  30.                         {
  31.                                 j = 0;
  32.                                 System.out.println();
  33.                         }
  34.                 }
  35.     }  
  36. }  
复制代码
回复 使用道具 举报
感谢楼主,,楼主好人。。
回复 使用道具 举报

这个方法好吊~
C++可以用容器来实现每个二进制位作为存储位,
荡是我不会c++的容器,
java刚开始学啥都不懂, 所以只好开一个好大的数组来存
回复 使用道具 举报
blensmile 发表于 2015-10-1 09:50
你这是最最基础的方法,代码复杂度低,但是时间复杂度太高了,数一大,运算量就急剧增长。 ...

受教了!
回复 使用道具 举报
看不懂 学一下        
回复 使用道具 举报
来膜拜大神的!!!!!!
回复 使用道具 举报
不错不错
回复 使用道具 举报

一起学习,一起进步~~~
回复 使用道具 举报
太子奕 发表于 2015-10-2 00:26
来膜拜大神的!!!!!!

你才大神,技术分都要够了,还在慢悠悠的积攒技术分呢
回复 使用道具 举报

你的黑马币和技术分好高啊,羡慕一个~~~
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马