南京专业网站制作多少钱,android应用程序开发教程,宁波网站建设公司哪家口碑好,南安住房与城乡建设部网站目录
一、最大公约数和最小公倍数
二、素数判断
三、同余
四、唯一分解定理
五、约数个数定理
六、约数和定理
五、快速幂
六、费马小定理
七、逆元 一、最大公约数和最小公倍数
文章链接#xff1a;最大公约数和最小公倍数
二、素数判断
文章链接#xff1a;在J…目录
一、最大公约数和最小公倍数
二、素数判断
三、同余
四、唯一分解定理
五、约数个数定理
六、约数和定理
五、快速幂
六、费马小定理
七、逆元 一、最大公约数和最小公倍数
文章链接最大公约数和最小公倍数
二、素数判断
文章链接在Java中判断素数
三、同余 同余是一个数学概念它描述了两个数在某个特定的模下具有相同的余数。在数学中我们使用符号≡来表示同余关系。具体来说对于给定的整数a、b和正整数m如果a与b除以m得到的余数相等即(a mod m) (b mod m)我们就说a与b在模m下是同余的。 四、唯一分解定理 该定理表明每个大于1的自然数都可以被唯一地表示为质数的乘积。 具体来说唯一分解定理可以表述为任何一个大于1的自然数n都可以写成质数的乘积形式即n p1^a1 * p2^a2 * … * pk^ak其中p1, p2, …, pk为质数a1, a2, …, ak为正整数并且这种表示方式是唯一的即如果将n分解成不同的质数乘积形式那么这些质数和指数也是唯一确定的。 例如对于自然数12它可以被分解为2^2 * 3^1其中2和3都是质数指数分别为2和1。而这种分解方式是唯一的即12不能被表示为其他质数乘积的形式。 import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;public class Main {static class node{int a,b;//a的b次方node(int a,int b){this.aa;this.bb;}}public static void main(String[] args){Scanner scannernew Scanner(System.in);int nscanner.nextInt();//输入的数输出是由多个质数的次方的乘积int tn;ArrayListnode enew ArrayList();for(int i2;in/i;i){if(n%i0){int ans0;while(n%i0){ans;n/i;}e.add(new node(i,ans));}}if(n1){e.add(new node(n,1));}System.out.print(t);for(int i0;ie.size();i){if(ie.size()-1){System.out.print(e.get(i).a^e.get(i).b);break;}System.out.print(e.get(i).a^e.get(i).b);}}
} 五、约数个数定理 约数个数定理是数论中的一个重要定理它给出了一个正整数的约数个数与其质因数分解有关的关系。具体来说如果一个正整数n可以分解为质数的乘积即n p1^a1 * p2^a2 * … * pk^ak其中p1、p2、…、pk为不同的质数a1、a2、…、ak为正整数则n的约数个数可以通过以下公式计算 约数个数 (a1 1) * (a2 1) * … * (ak 1) 其中(a1 1)、(a2 1)、…、(ak 1)分别表示每个质因数的指数加1后的值。 例如对于正整数12它可以分解为2^2 * 3^1因此它的约数个数为(21) * (11) 6。它的约数包括1、2、3、4、6和12。 六、约数和定理 通过某一个数字的唯一分解定理可以推出约数和定理。约数和定理是指对于任意一个正整数n它的所有约数的个数可以通过对n进行唯一分解后的指数加1的乘积来计算。 具体来说如果将正整数n进行唯一分解得到其质因数分解式为 n p1^a1 * p2^a2 * p3^a3 * … * pk^ak 其中p1, p2, p3, …, pk为不同的质数a1, a2, a3, …, ak为对应的指数。 根据唯一分解定理n的所有约数可以通过对指数进行组合得到。对于每个质因数pi它的指数ai可以取0到ai之间的任意整数这样就可以得到ai1个选择。因此n的所有约数的个数为(a11) * (a21) * (a31) * … * (ak1)。 以20为例将20进行唯一分解得到其质因数分解式为 20 2^2 * 5^1 其中2和5为不同的质数指数分别为2和1。 根据约数和定理20的所有约数的个数为(21) * (11) 6。即20的约数有6个分别为1、2、4、5、10和20。 也就是 12^0*5^01 22^0*5^15 32^1*5^02 42^1*5^110 52^2*5^04 62^2*5^120 五、快速幂
文章链接快速幂Java实现
六、费马小定理 费马小定理是数论中的一个重要定理它描述了在模运算下的一种特殊性质。具体来说费马小定理表明如果p是一个质数a是任意整数且不是p的倍数那么a的p-1次方除以p的余数等于1。 数学表达式为a^(p-1) ≡ 1 (mod p)------a^(p-1)%p1简单来说 这里的“≡”表示模运算下的等价关系即两个数除以p的余数相等。 举个例子来说明假设p7a3根据费马小定理我们可以计算3^6除以7的余数。计算过程如下 3^6 729 729 ÷ 7 104 余 1 因此根据费马小定理3^6除以7的余数等于1。 七、逆元 逆元是数论中的一个重要概念它指的是在模运算下对于给定的整数a和模数m存在一个整数b使得(a * b) % m 1。其中a称为原元b称为a的逆元。 举个例子来说明逆元的概念。假设我们要求解在模7下的逆元即找到一个整数b使得(a * b) % 7 1。如果我们取a 3那么可以发现3 * 5 1515除以7的余数为1所以5就是3在模7下的逆元。因此5是3的逆元。
