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

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

    震惊

    震惊

编辑推荐
这么神奇的代码就能过nod1186.。。 import java.util.Scanner; import java.math.*; public class M
质数又称素数,是数学中最常见的数字,即是指除1和它本身以外没有其它约数的数字 如 1 2 3 5 7 11 1
素数指的是因子只有1和本身的数(1不是素数),求解素数在数学上应用非常广泛,而求解n以内的素数也
JAVA 课上的一个作业:求比给定的数小的所有素数并打印出来 准备工作: 1)用Netbeans新建一个Java
源地址: http://www.cnblogs.com/yinghuochong/archive/2011/10/08/2203107.html 快速指数算法 和
一.辗转相除法 int gcd(int a,int b) { if(b==0) return a; return gcd(b,a%b); } 二.扩展欧几里德
为了学习Python,最好还是直接从写代码入手,解决的问题如下: 1、使用质数的定义求出所有小于等于1
上得厅堂,下得厨房,写得代码,翻得围墙,欢迎来到睿不可挡的每日一小练! 题目:求质数 内容: 试
题目: 写一个程序,找出前N个素数。比如N为100,则找出前100个素数。 分析 最基本的想法就是对1到N
题目: 写一个程序,找出前N个素数。比如N为100,则找出前100个素数。 分析 最基本的想法就是对1到N
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号