Posted on 2008-11-29 21:58
Qzi 閱讀(427)
評論(0) 編輯 收藏 所屬分類:
java foundation
最大公約數：使用輪轉相除法，它的原理是：（n1>n2）n1與n2的最大公約數等于n2與n1%n2的最大公約數，即
gcd(n1, n2)=gcd(n2, n1%n2)
最大公約數
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
素數篩選法：原理是：
1）0與1不是素數；
2）素數的2倍以上倍數不是素數
所以剔除這些剩下的就是素數了
素數篩選法
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是素數，則排除i的倍數
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