公约数,公倍数和素数的简单计算
为自己留作备份,省得用到的时候再去寻找
简单的计算最大公约数,最小公倍数和素数的.
?
public class MathTest {/** * 最大公约数<br> * Stein算法 * * @param a * @param b * @return */private static int gcd(int a, int b) {if (a == b) {return a;}int min = a < b ? a : b;int max = a < b ? b : a;if (min == 0) {// the base casereturn max;}if (max % 2 == 0 && min % 2 == 0) {// max and min are evenreturn 2 * gcd(max / 2, min / 2);}if (max % 2 == 0) {// only max is evenreturn gcd(max / 2, min);}if (min % 2 == 0) {// only min is evenreturn gcd(max, min / 2);}return gcd((max + min) / 2, (max - min) / 2);// max and min are odd}/** * 最小公倍数 * * @param a * @param b * @return */private static long lcm(int a, int b) {return 1L * a * b / gcd(a, b);}/** * 获取a后的下一个素数,不包括a,即使a是个素数. 没有考虑溢出 * * @param a * @return */private static int nextPrime(int a) {a++;while (!isPrime(a)) {a++;}return a;}/** * 判断一个数是否素数 * * @param n * @return */private static boolean isPrime(int n) {if (n <= 3) {return true;}if (n % 2 == 0) {return false;}int s = (int) Math.sqrt(n);for (int i = 3; i <= s; i++) {if (n % i == 0) {return false;}}return true;}private static class PrimeThread extends Thread {private int min;private int max;private CyclicBarrier cb;private AtomicInteger ai;@Overridepublic void run() {int n = 0;for (int m = min; m <= max; m++) {if (isPrime(m)) {n++;}}ai.addAndGet(n);System.out.println(min + "->" + max + " over!");try {cb.await();} catch (InterruptedException e) {e.printStackTrace();} catch (BrokenBarrierException e) {e.printStackTrace();}}}/** * @param args */public static void main(String[] args) {// 测试最大公约数和最小公倍数Random r = new Random();for (int i = 0; i < 10; i++) {int a = -1;int end = 99999999;while (a < 0) {a = r.nextInt(end);}int b = -1;while (b < 0) {b = r.nextInt(end);}System.out.println("a=" + a + ",b=" + b + ",gcd=" + gcd(a, b)+ ",lcm=" + lcm(a, b));}// 单线程求素数测试,较耗时int count = 100000000;// 测试1亿以内int n = 0;// 素数数量long l = System.currentTimeMillis();for (int i = 0; i < count; i++) {if (isPrime(i)) {n++;}if (i % (count / 10) == 0) {System.out.println(System.currentTimeMillis() - l + " : " + n);}}System.out.println(System.currentTimeMillis() - l + " : " + n);// 多线程求素数测试,较耗时final long l1 = System.currentTimeMillis();final AtomicInteger ai = new AtomicInteger(0);CyclicBarrier cb = new CyclicBarrier(4, new Runnable() {@Overridepublic void run() {System.out.println(System.currentTimeMillis() - l1 + " : "+ ai.get());}});int ts = 4;// 线程数int unit = count / ts;// 每个线程跑的数for (int i = 0; i < ts; i++) {PrimeThread pt = new PrimeThread();pt.min = i * unit;pt.max = (i + 1) * unit;pt.cb = cb;pt.ai = ai;pt.start();}// 求下一个素数测试,和jdk本身的对比int i = Integer.MAX_VALUE - 100;l = System.currentTimeMillis();BigInteger bi = new BigInteger("" + i);System.out.println(bi.nextProbablePrime());System.out.println(System.currentTimeMillis() - l);l = System.currentTimeMillis();System.out.println(nextPrime(i));System.out.println(System.currentTimeMillis() - l);}}?