【java每日一题,数论】最大公约数,最大质因数,欧拉筛

简介: 【java每日一题,数论】最大公约数,最大质因数,欧拉筛

求两个数a和b的最大公约数

int a=s.nextInt();
int b=s.nextInt();
int c,d;
while (true){
    if(a>b){
        c=a;
        d=b;
    }else {
        c=b;
        d=a;
    }
    a=c%d;
    b=d;
    if(a==0){
        System.out.println(b);
        break;
    }
}

a和b的最小公倍数求法,a乘b再除以它们的最大公约数

求一个数n的最大质因数

int n=s.nextInt();
int i,ans=0;
for( i=2;i*i<=n;i++){
    while (n%i==0){
        ans=i;
        n/=i;
    }
}
if(n>1){
    ans=n;
}
System.out.println(ans);


int n=s.nextInt();
int k = 2; 
while (n > 1){
    if (n % k == 0){
        n /= k;
    }
    else{
        k++; 
    }
}
System.out.println(ans);

求小于等于n的所有质数

int n=s.nextInt();
int[] primes=new int[n+1];
boolean[] st=new boolean[n+1];
int count=0;
for(int i=2;i<=n;i++){
  if(!st[i])primes[count++]=i;
  for(int j=0;i*primes[j]<=n;j++){
    st[i*primes[j]]=true;
    if(i%primes[j]==0)break;
  }
}
System.out.println(Arrays.toString(primes));
相关文章
|
Java
Java求最大公约数
Java求最大公约数
78 0
|
7月前
|
Java
Java:计算两个数的最大公约数和最小公倍数
Java:计算两个数的最大公约数和最小公倍数
|
7月前
|
人工智能 算法 Java
约数个数(c++, java)
约数个数(c++, java)
38 0
|
7月前
|
存储 Java
Java判断质数、求所有约数【蓝桥杯常用方法】
Java判断质数、求所有约数【蓝桥杯常用方法】
|
Java
阶乘约数+猴子分香蕉(蓝桥杯JAVA解法)
阶乘约数+猴子分香蕉(蓝桥杯JAVA解法)
147 0
|
Java
Java经典编程习题100例:第23例:求最大公约数
Java经典编程习题100例:第23例:求最大公约数
94 0
|
Java
求最大公约数和最小公倍数的做法(Java实现)
求最大公约数和最小公倍数的做法(Java实现)
228 0
|
Java
JAVA求两个数的最小公倍数和最大公约数(两种方法)
JAVA求两个数的最小公倍数和最大公约数(两种方法)
745 0
JAVA求两个数的最小公倍数和最大公约数(两种方法)
(JAVA编程练习):输入两个正整数m和n,求其最大公约数和最小公倍数。
(JAVA编程练习):输入两个正整数m和n,求其最大公约数和最小公倍数。
(JAVA编程练习):输入两个正整数m和n,求其最大公约数和最小公倍数。
ZZULIOJ-1062,最大公约数(Java)
ZZULIOJ-1062,最大公约数(Java)