数学知识----约数

文章目录

• • 试除法求一个数的所有约数
  • 约数的个数
  • 约数之和
  • 欧几里得算法(辗转相除法)--求最大公约数
  • 最小公倍数

试除法求一个数的所有约数

与试除法求一个数的所有质数类似

package luogu.数学知识.约数;import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;public class 试除法求一个数的所有约数 {static List<Integer> ans = new ArrayList<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();getDivisors(n);//对约数进行从小到大排序ans.sort(new Comparator<Integer>() {@Overridepublic int compare(Integer o1, Integer o2) {return o1-o2;}});for ( int i=0; i<ans.size(); i++ ) {System.out.println( ans.get(i) );}}public static void getDivisors( int n ) {for ( int i=1; i<=n/i; i++ ) {if ( n%i==0 ) {ans.add(i);//除去相同的除数if ( n/i!=i ) ans.add(n/i);}}}
}

约数的个数

每个数的指数取0时，该数为1，当所有数的指数为0时，这个约数为1，所以枚举从2开始枚举，如果从一开始会进入无限循环

package luogu.数学知识.约数;import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class 约数的个数 {//记录可以整除 N 的数的个数static Map<Integer, Integer> ans = new HashMap<>();//记录每个数的个数public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();getDivisor(n);//计数int res = 1;for (Integer integer :ans.keySet()) {res = res*(ans.get(integer)+1);}System.out.println( res );}public static void getDivisor( int n ) {for ( int i=2; i<n/i; i++ ) {while( n%i==0 ) {if ( ans.containsKey(i) ) ans.put(i, ans.get(i)+1);else ans.put(i, 1);n /= i;}}if ( n>1 ) { //判断是否还有剩余if ( ans.containsKey(n) ) ans.put(n, ans.get(n)+1);else ans.put(n, 1);}}
}

约数之和

package luogu.数学知识.约数;import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class 约数之和 {//记录可以整除 N 的数的个数static Map<Integer, Integer> ans = new HashMap<>();//记录每个数的个数public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();getDivisor(n);int res = divisorSum();//计算约数之和System.out.println( res );}//得到 n 的约数public static void getDivisor( int n ) {for ( int i=2; i<n/i; i++ ) {while( n%i==0 ) {if ( ans.containsKey(i) ) ans.put(i, ans.get(i)+1);else ans.put(i, 1);n /= i;}}if ( n>1 ) { //判断是否还有剩余if ( ans.containsKey(n) ) ans.put(n, ans.get(n)+1);else ans.put(n, 1);}}//计算约数之和public static int divisorSum() {int res = 1;//保存结果//遍历 mapfor ( Integer i : ans.keySet() ) {int sum_i = 1;for ( int j=1; j<=ans.get(i); j++ ) {sum_i += Math.pow( i, j );}res *= sum_i;}return res;}
}

欧几里得算法(辗转相除法)–求最大公约数

package luogu.数学知识.约数;import java.util.Scanner;public class 最大公约数 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int a = sc.nextInt();int b = sc.nextInt();int ans = gcd( a, b );System.out.println(ans);}//求 a,b 的最大公约数public static int gcd( int a, int b ) {//当b==0时，此时的a为最大公约数//b大于0 继续递归求解return b>0 ? gcd(b, a%b) : a;}
}

最小公倍数

例如，要求 a,b 的最大公约数和最小公倍数
a*b = 最大公约数 * 最小公倍数
所以，最小公倍数 = a*b / 最大公约数

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！