Posted on 2008-11-29 21:58
Qzi 閱讀(437)
評(píng)論(0) 編輯 收藏 所屬分類(lèi):
java foundation
最大公約數(shù)：使用輪轉(zhuǎn)相除法，它的原理是：（n1>n2）n1與n2的最大公約數(shù)等于n2與n1%n2的最大公約數(shù)，即
gcd(n1, n2)=gcd(n2, n1%n2)
最大公約數(shù)
1 public class MaxDivisor {
2 public static void main(String[] args){
3 int int1 = (int) Math.ceil(Math.random()*1000);
4 int int2 = (int) Math.ceil(Math.random()*1000);
5 System.out.print(int1+" " + int2+"\n");
6 System.out.println(findMaxDivisor(int1, int2));
7 }
8
9 public static int findMaxDivisor(int int1, int int2){
10 if(int1==int2) return int1;
11 else if(int1<int2){
12 int1 += int2;
13 int2 = int1 - int2;
14 int1 -= int2;
15 }
16 int temp;
17 while((temp = int1%int2) != 0){
18 return findMaxDivisor(int2, int1%int2);
19 }
20 return int2;
21 }
22 }
23
素?cái)?shù)篩選法：原理是：
1）0與1不是素?cái)?shù)；
2）素?cái)?shù)的2倍以上倍數(shù)不是素?cái)?shù)
所以剔除這些剩下的就是素?cái)?shù)了
素?cái)?shù)篩選法
1 public class PrimeNum {
2 public static void primeNum(){
3 boolean[] array = new boolean[6500];
4 for(int i = 0; i<array.length; i++){
5 array[i] = true;
6 }
7 array[0] = array[1] = false;
8 int end = (int) Math.ceil(Math.sqrt(array.length-1));
9 for(int i=2; i<end; i++){
10 if(array[i] == true)
11 for(int j = i+i; j<array.length; j+=i){//若i是素?cái)?shù)，則排除i的倍數(shù)
12 array[j] = false;
13 }
14 }
15 StringBuilder sb = new StringBuilder();
16 for(int i = 0; i<array.length; i++){
17 if(array[i] == true)
18 sb.append(i).append(" ");
19 }
20 System.out.println(sb.toString());
21 }
22
23 public static void main(String[] args){
24 primeNum();
25 }
26 }
27