1、判断质数
质数又称为素数，是指大于1的并且除了1和它本身外，没有其他因数的自然数。
判断一个数是否是质数
假设该数为n， 我们只需要判断内是否有n的因子。如果有，则n为合数，否则，n为质数。
这种方法被称为试除法， 即试着除一下所有可能的因子。
package action; public class demo { public static void main(String[] args) { System.out.println(isf(5));; } public static Boolean isf(int n){ if(n == 1) return false; for(int i = 2; i <= n / i; i++){ if(n % i == 0){ return false; } } return true; } }
2、分解质因数
根据算术基本定理又称唯一分解定理，对于任何一个合数， 我们都可以用几个质数的幂的乘积来表示。
接下来我们利用这个公式分解质因数。
设一个质数为p.如果n%p == 0，那么p就是n的一个质因数，接下来就是求p的指数，我们让n = n/p, 这样就从n中剔除了一个p,接着重复上述两步，直到n%p ！= 0
package action; public class demo { public static void main(String[] args) { isf(500); } public static void isf(int n) { for (int i = 2; i <= n / i; i++) { int a = 0, b = 0; while (n % i == 0) { a = i; n /= i; b++; } if (b > 0) { System.out.println(a + " " + b); } } if (n > 1) { System.out.println(n + " " + 1); } } }
3、快速幂
当我们计算时，常用的做法是对n连乘k次， 但如果k特别大，假如k = 1e6， 如果仍然对n连乘1e6次的话，时间消耗就太大了。那么我们如何在短时间内求出一个数的k次方呢。
求
快速幂
没有处理超大数
package action; public class demo { public static void main(String[] args) { System.out.println(ksm(2, 10)); } public static int ksm(int a, int b) { // 求 a^b int res = 1; // res保存结果 while (b != 0) { if ((b & 1) == 1) { // 如果k的二进制数的最后一位是 1。 比如1011 & 1 = 1 res = (res * a); } a = a * a;// 得到 a^1, a^2, a^4, a^8, ..... b = b >> 1; // 将b右移一位，去掉最低位。为了开始判断下一位。 } return res; } }
3、欧几里得定力
最大公约数、最小公倍数
package Action; public class demo { /* * 求最大公约数 最小公倍数 思路：根据欧几里得定理 gcd(a,b)=gcd(b,a%b); */ static int gcd(int a, int b) { // 出口：b=0;5和0的最大公约数是5 if (b == 0) return a; return gcd(b, a % b); } static int lcm(int a, int b) { return a * b / gcd(a, b); } public static void main(String[] args) { System.out.println(gcd(45, 35)); System.out.println(lcm(45, 35)); System.out.println(gcd(42, 60)); System.out.println(lcm(42, 60)); } }
4、海伦公式（求三角形面积）
