`
i2534
  • 浏览: 182495 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

公约数,公倍数和素数的简单计算

    博客分类:
  • util
 
阅读更多

为自己留作备份,省得用到的时候再去寻找

简单的计算最大公约数,最小公倍数和素数的.

 

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 case
			return max;
		}

		if (max % 2 == 0 && min % 2 == 0) {// max and min are even
			return 2 * gcd(max / 2, min / 2);
		}

		if (max % 2 == 0) {// only max is even
			return gcd(max / 2, min);
		}

		if (min % 2 == 0) {// only min is even
			return 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;

		@Override
		public 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() {

			@Override
			public 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);
	}

}
 
分享到:
评论

相关推荐

    求最大公约数和最小公倍数_素数_

    在编程领域,最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)是基础的数学概念,经常在算法设计和问题解决中使用。这里我们关注的是如何使用C++语言来实现计算这两个值的...

    求最大公约数 最小公倍数

    在C语言中,求解两个整数的最大公约数(GCD)和最小公倍数(LCM)是常见的编程任务。以下是对给定代码片段的分析及扩展解释。 #### 代码解读 ```c #include void main() { int p, r, n, m, temp; printf("请输入...

    罗列素数&计算PI&最大公约数&最小公倍数

    这个项目"罗列素数&计算PI&最大公约数&最小公倍数"就是一个很好的例子,它涵盖了四个核心的数学概念:素数、圆周率(PI)、最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)...

    最大公约数和最小倍数.docx

    b)互质•如果两个数的最大公约数是1,则称这两个数互质①分解质因数法例:求24和60的最大公约数与最小公倍数每个合数都可以写成几个质数相乘的形式最大公约数是两个数所有公有质因数的乘积24和60公有的质因数是2、2...

    排序 最小公倍数 最大公约数 素数C语言算法

    总的来说,排序、最小公倍数、最大公约数和素数判断是C语言编程中的基础算法,理解和掌握它们对于任何IT从业者都至关重要。通过实践和研究,我们可以不断精进自己的编程能力,为未来的开发工作打下坚实的基础。

    最大公约数和最小公倍数.doc

    ### 最大公约数和最小公倍数知识点详解 #### 一、基本定义及概念 - **整数倍数与约数**:如果整数\(a\)能够被整数\(b\)(\(b \neq 0\))整除,那么我们说\(a\)是\(b\)的倍数,\(b\)是\(a\)的约数。 - **公约数与...

    最大公约数和最小公倍数数学知识.doc

    最大公约数(Greatest Common Divisor,GCD)与最小公倍数(Least Common Multiple,LCM)是...通过这些练习题,学生可以深入理解最大公约数和最小公倍数的概念,掌握它们的计算方法,并能够在实际问题中应用这些知识。

    最大公约数和最小公倍数复习PPT课件.pptx

    【知识点详解】 ...通过以上知识点的阐述,我们可以了解到最大公约数和最小公倍数的概念、计算方法以及它们在数论中的应用。这些知识对于解决涉及整数除法的问题非常关键,是数学基础教育的重要组成部分。

    短除法求最大公约数、最小公倍数.doc

    【短除法求最大公约数、最小公倍数】是一种在数学中求解两个或多个整数的最大公约数(Greatest Common Divisor, GCD)和最小公倍数(Least Common Multiple, LCM)的简便方法。这种方法尤其适用于求解较大整数之间的...

    小学六年级最大公约数与最小公倍数复习题精选.doc

    【最大公约数与最小公倍数】是小学六年级数学中的一个重要概念,涉及到数的整除性质和因数分解。最大公约数(Greatest Common Divisor, GCD)是指两个或多个非零整数共有约数中最大的一个,而最小公倍数(Least ...

    JAVA基础 第一篇:素数、合数、质数分解、最大公约数、最小公倍数.docx

    总之,理解并熟练掌握素数、合数、质数分解、最大公约数和最小公倍数的概念及计算方法,对Java程序员来说是至关重要的。这些基础知识不仅应用于初学者的练习,还常常出现在高级算法和数据结构中,是编程能力提升的...

    最大公约数和最小公倍数【新课标人教版】精选.doc

    最大公约数和最小公倍数是数学中基本的数论概念,主要研究的是整数之间的约分和通分关系。在解决与之相关的数学问题时,我们通常会使用以下方法: 1. 最大公约数(Greatest Common Divisor, GCD):两个或多个整数...

    最大公约数和最小公倍数练习题--姓名.doc

    【最大公约数(GCD)和最小公倍数(LCM)】 最大公约数是指能同时整除两个或多个整数的最大正整数。最小公倍数则是指能被两个或多个整数共同整除的最小正整数。两者在数学中有着广泛的应用,尤其是在数论和算法设计中。 ...

    最大公约数的实例

    在实际应用中,最大公约数可以用来简化比例、求解同余方程、计算最小公倍数等。在软件开发中,了解和掌握如何求解最大公约数是提升编程能力的基础。 这个实例适合初学者,通过实践可以帮助理解最大公约数的概念,...

    Python实现利用最大公约数求三个正整数的最小公倍数示例

    在解决这个问题的过程中,我们首先需要了解如何计算两个数的最大公约数(Greatest Common Divisor, GCD),因为最大公约数和最小公倍数之间存在着密切的关系。 #### 关键概念解释 1. **最大公约数(GCD)**: - ...

    PTA-公因数与公约数

    最大公因数(Greatest Common Divisor,简称GCD),也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一...编写程序,从键盘读入两个整数m和n(使用空格分隔),然后输出m和n的最大公约数和最小公倍数到屏幕。

    输入两个正整数m和n求其最大公约数和最小公倍数.pdf

    1. **最大公约数(GCD)和最小公倍数(LCM)**:使用欧几里得算法可以计算两个正整数的最大公约数,而最小公倍数可以通过两数乘积除以它们的最大公约数得到。 2. **字符计数**:在字符串处理中,统计字母、空格、...

Global site tag (gtag.js) - Google Analytics