Java算法笔记_012:埃拉(Ella)托色尼筛选法(Java)

1 问题讲述

Compute the Greatest Common Divisor of
Two Integers using Sieve of Eratosthenes.

翻:使用Ella托色尼筛选法总括两独整数的最大公约数。(PS:最大公约数也如太酷公因数,指区区单或多单整数共有约数着最好要命的一个)

 

 


2 解决方案

2.1 埃拉(Ella)托色尼筛选法原理简介

引用自百度百科:

Ella托色尼筛选法(the Sieve of
Eratosthenes)简称埃氏筛法,是古希腊地国学家Ella托色尼(Eratosthenes
274B.C.~194B.C.)指出的如出一辙种筛选法。
是指向本数列中之自然数而进行的,用于求一定限制外之质数,它的容斥原理的完备性条件是p=H~。

现实求取质数的思索:

(1)先将1剔除(现今数学界1既无是质数也无是合数)

(2)读取队列中时最为小之频繁2,然后把2的倍数删去

(3)读取队列中即极其小之勤3,然后把3之倍数删去

(4)读取队列中即不过小之再三5,然后将5底倍数删去

(5)如上所述直到需求的限量外拥有的频繁均删除或读取

下边看一下执上述手续求不超100底装有质数的一个示意图:

Java 1

 

 

2.2 具体编码

正文求取六只数的最大公约数,采取质因数分解法:把每个数分别分解质因数,再将各数中的周国有质因数提取出来连乘,所得的积压就是当时几乎独数之最大公约数

诸如:求24和60的最大公约数,先分解质因数,得24=2×2×2×3,60=2×2×3×5,24与60底全方位国有的质因数是2、2、3,它们的积压是2×2×3=12,所以,(24,60)=12。

此间,第一步,先用Ella托色尼筛选法求取不大于数A的有所质数,然后从那一个质数中摘A的装有质因数;第二步,依据第一步思想求取数B的兼具质因数;第三步,求取数A和数B公共质以累;第四步,输出数A和数B的最大公约数。

现实代码如下:

Java, 

package com.liuzhen.ex1;

import java.util.Scanner;

public class SieveOfEratosthenes {
    //返回一维数组,数组中的元素为不大于n的所有质数
    public static int[] getPrime(int n){
        int[] result1 = new int[n];   //定义一个一维数组,并从第2个元素依次初始化为相应的自然数
        for(int i = 2;i < n+1;i++){    
            result1[i-1] = i;
        }
        for(int i = 2;i < n;i++){
            for(int j = i+1;j < n+1;j++){
                if(j % i == 0)          //如果j能够整除i,使result[j-1]等于0
                    result1[j-1] = 0;
            }
        }
        int[] result2 = getNoneZero(result1);  //除去result数组中所有0元素
        return result2;     //数组中非零元素即为不大于n的所有质数
    }

    //返回一维数组,该数组的元素为参数数组中所有不为0的元素值
    public static int[] getNoneZero(int[] A){
        int len = 0; 
        for(int i = 0;i < A.length;i++){
            if(A[i] != 0)
                len = len+1;
        }
        int[] result = new int[len];
        int k = 0;
        for(int i = 0;i < A.length;i++){
            if(A[i] != 0){
                result[k] = A[i];
                k++;
            }
        }
        return result;
    }

    //求取一个数n的所有质因数(eg:24=2×2×2×3,则result[] = {2,2,2,3})
    public static int[] getNprime(int n){
        int[] primes = getPrime(n);
        int[] result;        //最终返回结果集
        int len = 0;         //返回结果集数组长度,初始化为0
        for(int i = 0;i < primes.length;i++){
            int temp = n;
            while(temp % primes[i] == 0){
                temp = temp/primes[i];
                len++;
            }
        }
        result = new int[len];
        int k = 0;
        for(int i = 0;i < primes.length;i++){
            int temp = n;
            while(temp % primes[i] == 0){
                temp = temp/primes[i];
                result[k] = primes[i];
                k++;
            }
        }
        return result;
    }

    //返回两个一维数组中所有共同元素
    public static int[] getCommonPrime(int[] A , int[] B){
        int[] result;
        int lenA = A.length;
        int lenB = B.length;
        if(lenA < lenB){
            result = new int[lenA];
            for(int i = 0;i < lenA;i++){
                int temp = A[i];
                for(int j = 0;j < lenB;j++){
                    if(temp == B[j]){
                        result[i] = A[i];
                        B[j] = 0;
                        break;
                    }
                }
            }
        }
        else{
            result = new int[lenB];
            for(int i = 0;i < lenB;i++){
                int temp = B[i];
                for(int j = 0;j < lenA;j++){
                    if(temp == A[j]){
                        result[i] = B[i];
                        A[j] = 0;
                        break;
                    }
                }
            }
        }
        int[] result1 = getNoneZero(result);
        return result1;
    }

    //求取数A和B的最大公约数
    public static void getMaxCommonDivisor(int A,int B){
        int[] primesA =  getNprime(A);  //数A所有质因子
        int[] primesB = getNprime(B);   //数B所有质因子
        int[] resultPrime = getCommonPrime(primesA,primesB);  //数A和数B的公共质因数
        int maxCommonDivisor = 1;
        System.out.println(A+"和"+B+"的公共质因数为:");
        for(int i = 0;i < resultPrime.length;i++){
            maxCommonDivisor *= resultPrime[i];
            System.out.print(resultPrime[i]+"\t");
        }
        System.out.println();
        System.out.print(A+"和"+B+"的最大公约数为:"+maxCommonDivisor);
    }

    public static void main(String[] args){
        System.out.println("请输入数字A和数字B的值:");
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        getMaxCommonDivisor(a,b);
    }
}

 

运转结果:

请输入数字A和数字B的值:
100 60
100和60的公共质因数为:
2    2    5    
100和60的最大公约数为:20


请输入数字A和数字B的值:
60 48
60和48的公共质因数为:
2    2    3    
60和48的最大公约数为:12


请输入数字A和数字B的值:
120 54
120和54的公共质因数为:
2    3    
120和54的最大公约数为:6

 

相关文章