欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

辅导资料 整数的基本性质与应用(最大公约数 最小公倍数 素数 )

程序员文章站 2022-06-20 12:17:31
...

一、最大公约数:
1.(不适用于long类型的数据)
辅导资料 整数的基本性质与应用(最大公约数 最小公倍数 素数 )

代码:

package sf_1;
public class Main {
    //求最大公约数
    public static void main(String[] args) {
        /*
         * 求a和b的最大公约数
         * 则从可能 的数a开始一直到1.
         * 既能把a整除,又能把b整除,则为最大公约数。
         */
        int a=15;
        int b=40;
        for(int i=a;i>=1;i--){
            if(a%i==0&&b%i==0){
                System.out.print(i);
                break;
        }
        }

}

2.辗转相除法

package sf_2;
public class Main {
    /*
     *求a和b的最大公约数
     * 
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        /*
         * 辗转相除法 
         *有一个数字i能够a,b;那么这个数字i也可以整除b-a(假设b>a) 
         * a=ka*i;
         * b=kb*i;
         * b-a=(kb-ka)*i;
         * 
         * 
         * 则此时[a,b]--[b-a,b](b减去1个a可以,则b减去多个a也可以)-----[b%a,a]
         * 
         * [15,40]--[10,15]--[5,10]--[0,5]
         */
        int a=15;
        int b=40;
        for(;;){
            if(a==0){
                System.out.print(b);
                break;
            }
            int temp=a;
            a=b%a;//较大的数字对于较小的数字取模,当作新的较小的数字
            b=temp;
        }
    }
}

3.递归法

package sf_3;

public class Main {

    /**
     * @param args
     */
    public static int gcd(int a,int b){
        if(a==0)
            return b;
        return gcd(b%a,a);
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.print(gcd(15,40));
    }

}

二、最小公倍数

/*
 * 最小公倍数=(a*b)/gcd(a,b);
 * a=ka*i;   i为最大公约数
 * b=kb*i;
 * a*b=ka*kb*i*i  ka*kb*i为最小公倍数
 * 
 */

三、a的n次幂

package sf_4;
public class Main {
    public static int f(int n,int a,int p){
        int x=1;
        for(int i=0;i<n;i++)
            x=(x*a)%p;
        return x;
    }
    /*
     * (a+b)%p=(a%p+b%p)%p;
     * (a*b)%p=(a%p)*(b%p)%p;
     */
    public static void main(String[] args) {
        //a的n次幂
        System.out.print(f(30,5,17));
    }
}

四、素数(筛子法)

package sf_5;
public class Main {
    /*
     * 2 3 4 5 6 7 8 9 10 11 12 13......
     * 2 3 _ 5 _ 7 _ 9 _  11 _  13......
     * 2 _ _ 5 _ 7 _ _ _  11 _  13......
     * ..............
     */
    public static void main(String[] args) {
        int N=1000*1000*10;
        int x=10001;
        byte[] a=new byte[N];
        for(int i=2;i<N/2;i++){
            if(a[i]==1)//和数没有资格参加
                continue;
            for(int k=2;k<=N/i;k++)
            {
                if(i*k<N)
                    a[i*k]=1;
            }
        }
        int m=0;
        for(int i=2;i<N;i++){
            if(a[i]==0)
            {
                m++;
                if(m==x){
                    System.out.println(i);
                    break;
                }
            }   
        }
        System.out.print(m);
    }
}