`
fancyboy2050
  • 浏览: 240534 次
  • 性别: Icon_minigender_1
  • 来自: 皇城根儿下
社区版块
存档分类
最新评论

java求质数

    博客分类:
  • java
阅读更多
这两天JE求质数的帖子火了好几个哈

先介绍下质数的解释:
就是在所有比1大的整数中,除了1和它本身以外,不再有别的约数,这种整数叫做质数,质数又叫做素数。

质数判断技巧:
先找一个数m,使m的平方大于n,再用<=m的质数去除n(n即为被除数),如果都不能整除,则n必然是质数。

贴代码:
public static void main(String args[]){
		long start = System.currentTimeMillis();
// 走质数判断技巧的过程
		List<Integer> list = new ArrayList<Integer>();
		list.add(2);
		for(int i=3; i<500000 ; i+=2){
			if(isPrime(i, list)){
				list.add(i);
			}
		}
		for(int x : list){
			System.out.print(x+",");
		}
// 递归
		for(int i=3; i<500000; i+=2){
			boolean boo = true;
			for(int j=2; j<i; j++){
				if(i%j == 0){
					boo = false;
					break;
				}
			}
			if(boo){
				System.out.print(i+",");
			}
		}
// 开平方,求余
		for(int i=3; i<500000; i+=2){
			if(offPrime(i)){
				System.out.print(i+",");
			}
		}
		long end = System.currentTimeMillis();
		System.out.println();
		System.out.println(end - start);
	}

public static boolean isPrime(int i, List<Integer> ii){
		for(int j : ii){
			if(j*j <= i){
				if(i%j == 0){
					return false;
				}
			}else{
				return true;
			}
		}
		return true;
	}

public static boolean offPrime(int n){
		for(int i=3; i*i <= n; i++){
			if(n%i==0){
				return false;
			}
		}
		return true;
	}

效率不说了,mark一下
分享到:
评论

相关推荐

    java求素数的经典算法

    ### Java求素数的经典算法 #### 一、引言 素数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的数。求解素数是计算机科学中的一个经典问题,特别是在密码学等领域有着重要的应用价值。Java作为一门流行...

    java求质数实例程序

    java 求质数实例程序 求质数 源代码 简单易懂

    java求素数

    java,很简单的算法求素数

    Java求质数的几种常用算法分析

    "Java求质数的几种常用算法分析" 本文主要介绍了Java中求质数的几种常用算法,并结合实例形式分析了三种比较常见的求质数算法原理及相关实现技巧。 一、根据质数的定义求质数 质数的定义是:只能被1或者自身整除...

    求质数 java 简单的java程序

    这是一个用java编写的控制台程序,可以求一个数是不是质数,并且把这个数按递减顺序求,一直求到1,一次性的显示判断

    求素数的Java表示

    java的10000以内的数的素数的求法,算法简单易懂

    用java求素数

    利用java编程实现素数的求解,比较方便,代码较小,可以用于其他地方。

    Java大素数判断低时间复杂度

    Java 大素数 判断 低时间复杂度.

    sushu.rar_java 素数_求素数

    "java 素数_求素数"这部分描述了压缩文件的核心内容,即用Java语言实现的一个程序,用于找出1到50之间的所有素数。 素数是大于1且只能被1和其自身整除的自然数,例如2、3、5、7、11等。在计算机科学中,尤其是算法...

    java语言实现求素数的原根

    在Java语言中实现求素数的原根,我们需要以下步骤: 1. **素数判断**:首先需要一个函数来判断输入的数是否为素数。可以采用试除法,从2到这个数的平方根,如果发现有任何能整除的数,那么这个数不是素数。如果没有...

    【Java】求1-100范围内的素数递归方法

    【Java】求1-100范围内的素数递归方法代码例子。分享,感谢。

    求素数的方法

    求1到100的素数,不过这个算法可能不是很好,另外,还要有,5个换行输出

    69.java找素数.zip

    69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数.zip69.java找素数...

    java使用筛选法求n以内的素数示例(java求素数)

    总之,Java中的筛选法求素数是一种实用的算法,它结合了数学原理和编程技巧,能够有效地找出一定范围内的所有素数。通过理解并实践这段代码,开发者可以深入理解素数筛选法的实现细节,并将其应用到更广泛的编程场景...

    Java 求指定范围内素数的个数

    Java 求指定范围内素数的个数,接受用户从键盘输入所求范围,计算出该范围内素数的个数。

    Java版求质数

    判断一个数是否为质数的静态函数 自己所写的最优算法

    Java求100之内的素数.rar

    本示例中,我们探讨的主题是如何使用Java编程语言来找出100之内的所有素数。素数是自然数中的一个特殊类别,它们只能被1和自身整除,没有其他正因数。在数学上,2是最小的素数,而1则不被认为是素数。 在Java中,...

    利用JAVA,求素数和。

    在编程领域,尤其是在Java语言中,计算特定范围内素数之和是一个常见的算法问题。这个问题的目的是找到第n个到第m个素数(包括n和m)的总和,其中0 。在这个过程中,我们需要掌握以下几个关键知识点: 1. **素数...

    Java中素数的写法

    关于Java中素数的概念,及Java代码的写法,写了几种方法

    素数Java程序,用于Java第二版教材上的习题求Java素数

    这个压缩包文件“素数”可能包含了一个或多个Java源代码文件,用于解决Java第二版教材中的素数相关习题。以下将详细介绍Java编程中如何实现素数检测,并扩展到相关的数学和算法知识。 1. **素数判断算法**: - 最...

Global site tag (gtag.js) - Google Analytics