1. 
   
2. class prime {
   
3. 
   
4.         static void prt(String s){
   
5.                 System.out.print(s);
   
6.         }
   
7. /*
   
8. 基本思想:
   
9. 1.合数都可以彻底分解为质数与质数的乘积,即合数总是可以找到至少一个质数使得这个合数%素数==0
   
10. 2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有素数),如果没有一个能除尽,则x是素数
    
11. 3.任何合数成对的因数中,必然有一个小于等于这个数开方的根,例如sqrt(12)=3.4,12=2*6=3*4,2和3都小于3.4
    
12.   所以只需要比较到sqrt(x)就可以确定这个数是不是素数了
    
13. 
    
14. 基于以上思想,创建一个数组由小到大存储已经确认的素数,即存储,也用来运算,代价是要使用比较多的内存
    
15. */
    
16.         private static void primeTest1(int a){
    
17.                 int i = 0;
    
18.                 int j = 0;
    
19.                 int sqrtNum = 0;
    
20.                 int arryNum = (int)(a*1.2/Math.log((double)a));
    
21.                 int prim[] = new int[arryNum];        //创建一个数组
    
22.                 for(i = 0;i<arryNum;i++)                                
    
23.                         prim[i] = i+2;                             //数组初始化,prim[0] = 2...
    
24.                 int countNum = 2;                            //已经有2,3 这2个素数
    
25.                 long startTime=System.currentTimeMillis();//用于计时
    
26.                 for(i=5;i<a;i+=2){                               //从5开始,步长为2,直接排除偶数参与运算
    
27.                         sqrtNum = (int)Math.sqrt(i);      //计算i开方的值,转换为int型
    
28.                         for(j=1;j<=countNum;j++){       //prim[0]=2,prim[1]=3,已排除偶数,故从3开始参与运算,
    
29.                                 if((i%(prim[j]))==0)             //i被prim中存储的素数除尽,证明它不是素数,跳出循环
    
30.                                         break;
    
31.                                 if( prim[j] > sqrtNum ){       //除数的素数值已经大于被除数的开方值,判断这个数是素数
    
32.                                         prim[countNum] = i;    //存储
    
33.                                         countNum++;              //
    
34.                                         break;                           //完成质数的确认,跳出循环
    
35.                                 }
    
36.                         }
    
37.                 }
    
38. 
    
39.                 System.out.println("\nTest1 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
    
40.                 i = 0;
    
41.                 System.out.println("countNum : " + countNum);   //打印素数总数
    
42. //                while(i<count){               //打印每个素数
    
43. //                        System.out.print(prim[i]+"\t");                                       
    
44. //                        i++;
    
45. //                }
    
46.         }
    
47. /*
    
48. 基本思想:
    
49. 1.所有素数一定是奇数,因为偶数可以被2整除
    
50. 2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有奇数),如果没有一个能除尽,则x是素数
    
51. 3.任何合数成对的因数中,必然有一个小于等于这个数开方的根,例如sqrt(12)=3.4,12=2*6=3*4,2和3都小于3.4
    
52.   所以只需要比较到sqrt(x)就可以确定这个数是不是素数了
    
53. */
    
54.         private static void primeTest2(int a){
    
55.                 int i;
    
56.                 int j;
    
57.                 int countNum = 2;
    
58.                 int sqrtNum =0;
    
59. //                System.out.print("2\t3\t");   //需要输出解除注释,
    
60.                 long startTime=System.currentTimeMillis();
    
61.                 for( i = 5;i<a;i+=2){         //从5开始,步长为2,直接排除偶数参与运算
    
62.                         sqrtNum = (int)Math.sqrt(i);
    
63.                         for(j = 3;j<i;j+=2){
    
64.                                 if(i%j ==0)
    
65.                                         break;
    
66.                                 if(j > sqrtNum){
    
67.                                         countNum++;
    
68. //                                        System.out.print(i + "\t");   //需要输出解除注释,
    
69.                                         break;
    
70.                                 }
    
71.                         }
    
72.                 }
    
73.                 System.out.println("\nTest2 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
    
74.                 System.out.println("countNum : " + countNum);
    
75.         }
    
76. 
    
77. /*
    
78. 基本思想:
    
79. 1.所有素数一定是奇数,因为偶数可以被2整除
    
80. 2.拿到任意一个在取值范围以内的数字x,用x%(比x小的所有奇数),如果没有一个能除尽,则x是素数
    
81. */
    
82.         private static void primeTest3(int a){
    
83.                 int i;
    
84.                 int j;
    
85.                 int countNum = 2;
    
86. //                System.out.print("2\t3\t");   //需要输出解除注释,
    
87.                 long startTime=System.currentTimeMillis();
    
88.                 for( i = 5;i<a;i+=2){                //从5开始,步长为2,直接排除偶数参与运算
    
89.                         for(j = 3;j<i;j+=2){
    
90.                                 if(i%j ==0)
    
91.                                         break;
    
92.                                 if(j+2 == i){
    
93.                                         countNum++;
    
94. //                                        System.out.print(i + "\t");    //需要输出解除注释,
    
95.                                         break;
    
96.                                 }
    
97.                         }
    
98.                 }
    
99.                 System.out.println("\nTest3 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
    
100.                 System.out.println("countNum : " + countNum);
     
101.         }
     
102. 
     
103. /*
     
104. 基本思想:
     
105. 拿到任意一个在取值范围以内的数字x,用x%(比x小的所有数),如果没有一个能除尽,则x是素数
     
106. */
     
107.         private static void primeTest4(int a){
     
108.                 int i;
     
109.                 int j;
     
110.                 int countNum = 1;                        //此时默认2是素数
     
111. //                System.out.print("2\t");
     
112.                 long startTime=System.currentTimeMillis();
     
113.                 for( i = 3;i<a;i++){        //从3开始,因为2%2==0,会影响判断
     
114.                         for(j = 2;j<i;j++){
     
115.                                 if(i%j ==0)                                
     
116.                                         break;
     
117.                                 if(j+1 == i){    //判断到比i小1,这时可以确认它是素数
     
118.                                         countNum++;
     
119. //                                        System.out.print(i + "\t"); //需要输出解除注释,
     
120.                                         break;
     
121.                                 }
     
122.                         }
     
123.                 }
     
124.                 System.out.println("\nTest4 runtime :"+(System.currentTimeMillis()-startTime)/1000f+"s");
     
125.                 System.out.println("countNum : " + countNum);
     
126.         }
     
127. 
     
128. /*
     
129. 
     
130. 
     
131. */
     
132.         public static void main(String args[]) {
     
133.                
     
134.                 int maxNum = 300000;        //通过这里设置取值上限,完成4种方法运行时间的实验
     
135.                 prt("Hello Cruel World!\n");
     
136.                 primeTest1(maxNum);
     
137.                 primeTest2(maxNum);
     
138.                 primeTest3(maxNum);
     
139.                 primeTest4(maxNum);
     
140.         }
     
141. 
     
142. }

复制代码

llwhcm 发表于 2015-10-2 01:52
不错不错

你的黑马币和技术分好高啊,羡慕一个~~~

太子奕 发表于 2015-10-2 00:26
来膜拜大神的！！！！！！

你才大神,技术分都要够了,还在慢悠悠的积攒技术分呢

曾经的星空 发表于 2015-10-1 23:50
看不懂 学一下

一起学习,一起进步~~~

不错不错

来膜拜大神的！！！！！！

看不懂 学一下        

blensmile 发表于 2015-10-1 09:50
你这是最最基础的方法，代码复杂度低，但是时间复杂度太高了，数一大，运算量就急剧增长。 ...

受教了！

朦胧色彩 发表于 2015-10-1 18:48

这个方法好吊~
C++可以用容器来实现每个二进制位作为存储位,
荡是我不会c++的容器,
java刚开始学啥都不懂, 所以只好开一个好大的数组来存

感谢楼主，，楼主好人。。

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. }  

复制代码

虽然有点复杂，但是感觉很有想法的样子

看不懂 学一下        

感谢楼主提供的思路，认真学习一下！

然子 发表于 2015-10-1 09:14

你这是最最基础的方法，代码复杂度低，但是时间复杂度太高了，数一大，运算量就急剧增长。

然子 发表于 2015-10-1 09:14

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

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. }

复制代码

这个方法太麻烦了吧。。