当前位置:首页 > 开发 > 编程语言 > 算法 > 正文

java求质数(素数)的快速算法

发表于: 2012-05-05   作者:366674654   来源:转载   浏览:
摘要: public static List<Integer> ListPrime(int n) { /* * false为质数,true为合数 */ boolean[] primeList = new boolean[n + 1]; for (int i = 2; i <= n; i++) { if (!primeList[i]) {
	public static List<Integer> ListPrime(int n) {
		/*
		 * false为质数,true为合数
		 */
		boolean[] primeList = new boolean[n + 1];

		for (int i = 2; i <= n; i++) {
			if (!primeList[i]) {

				int j = i * i;

				if (j > n) // 所有合数都已被标记
					break;
				if (i > 2) {
					/*
					 * 将所有能被此质数整除的奇数标记为合数
					 */
					while (j <= n) {
						primeList[j] = true;
						j = j + i + i;
					}
				} else {
					/*
					 * 将所有大于2的偶数标记为合数
					 */
					while (j <= n) {
						primeList[j] = true;
						j = j + i;
					}
				}
			}
		}
		List<Integer> listPrime = new LinkedList<Integer>();
		if( n > 1 )
			listPrime.add(2);
		for (int i = 3; i <= n; i += 2) {
			if (!primeList[i]) {
				listPrime.add(i);
			}
		}
		System.out.println(listPrime.size());
		return listPrime;
	}

java求质数(素数)的快速算法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号