Posted on 2008-11-29 21:58
Qzi 阅读(421)
评论(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