这两天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求素数的经典算法java求素数的经典算法java求素数的经典算法
java 求质数实例程序 求质数 源代码 简单易懂
java,很简单的算法求素数
这是一个用java编写的控制台程序,可以求一个数是不是质数,并且把这个数按递减顺序求,一直求到1,一次性的显示判断
java的10000以内的数的素数的求法,算法简单易懂
利用java编程实现素数的求解,比较方便,代码较小,可以用于其他地方。
主要介绍了Java求质数的几种常用算法,结合实例形式分析了三种比较常见的求质数算法原理及相关实现技巧,需要的朋友可以参考下
Java 大素数 判断 低时间复杂度.
主要介绍了java使用筛选法求n以内的素数示例(java求素数),需要的朋友可以参考下
java语言实现求素数的原根的源代码 输入一个素数 求出他所有的原根 密码学相关 java语言实现求素数的原根的源代码 输入一个素数 求出他所有的原根 密码学相关
【Java】求1-100范围内的素数递归方法代码例子。分享,感谢。
Java求100之内的素数,素数是只能被1和自身整除的数,运用for循环和if条件语句,即可轻松解决这个数学问题,求素数也是初学Java时频率较高的测试题,新手看看哦。
求1到100的素数,不过这个算法可能不是很好,另外,还要有,5个换行输出
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 求指定范围内素数的个数,接受用户从键盘输入所求范围,计算出该范围内素数的个数。
判断一个数是否为质数的静态函数 自己所写的最优算法
素数Java程序,用于Java第二版教材上的习题求Java素数
关于Java中素数的概念,及Java代码的写法,写了几种方法
素数是指因数只有1和本身的数字,这篇文章主要介绍了java求100以内的素数示例,需要的朋友可以参考下