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

Java 求素数运算

发表于: 2012-06-26   作者:周凡杨   来源:转载   浏览:
摘要: 网络上对求素数之解数不胜数,我在此总结归纳一下,同时对一些编码,加以改进,效率有成倍热提高。 第一种:   原理: 6N(+-)1法         任何一个自然数,总可以表示成为如下的形式之一: 6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)   

网络上对求素数之解数不胜数,我在此总结归纳一下,同时对一些编码,加以改进,效率有成倍热提高。


第一种:

 

原理: 6N(+-)1法
 
      任何一个自然数,总可以表示成为如下的形式之一: 6N,6N+1,6N+2,6N+3,6N+4,6N+5 (N=0,1,2,…)
      显然,当N≥1时,6N,6N+2,6N+3,6N+4都不是素数,只有形如6N+1和6N+5的自然数有可能是素数。所以,  除了2和3之外, 所有的素数都可以表示成6N±1的形式(N为自然数)。 根据上述分析,我们可以构造另一面筛子,  只对形如6N±1的自然数进行筛选,这样就可以大大减少筛选的次数,从而进一步提高程序的运行效率和速度。
      
      在程序上,我们可以用一个二重循环实现这一点,外循环i按3的倍数递增,内循环j为0-1的循环,则2(i+j)-1恰好就是形如6N±1的自然数。

 

 

源码:

 private static void method3(int num) {  
        long start = System.currentTimeMillis();  
        label1: for (int n = 1;; n++) {  
            label2: for (int m = 0; m <= 1; m++) {  
		                int tmp = (3 * n + m)<< 1 - 1;    //这里用位移"<<1"代替"*2" ,效率会有明显提高
		                if (tmp > num)  
		                    break label1;  
		                for (int k = 2; k * k <= tmp; k++)  
		                    if (tmp % k == 0)  
		                        if (m == 0)  
		                            continue label2;  
		                        else  
		                            continue label1;  
		                System.out.print(tmp + " ");  
            }  
        }  
        System.out.println("耗时:"+(System.currentTimeMillis()-start));  
    }  

 

   测试结果: num = 50 0000;运行100次取平均值:

 

耗时:223

 

 

第二种:

public long method4(int num) {  
	long bTime = System.currentTimeMillis();
		
	ArrayList<Integer> al = new ArrayList<Integer>(num>>1); //申请预计空间,避免扩容  
       
        for (int i = 2; i <= num; i++) {  
            boolean ok = true;  
            for (int t : al) {            // 用已有质数集作判断,减少比较次数  
                if (i % t == 0) {  
                    ok = false;  
                    break;  
                }  
                if (t * t > i) {        // 这句很关键,用小于其平方根的数整除  
                    break;  
                }  
            }  
            if (ok) {  
                al.add(i);  
            }  
        }  
	    
	    return System.currentTimeMillis()-bTime;
	}
 

测试结果: num= 50 0000;  运行100次取平均值:

 

耗时:376

 

 

 

Java 求素数运算

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
JAVA 课上的一个作业:求比给定的数小的所有素数并打印出来 准备工作: 1)用Netbeans新建一个Java
public static void prime(int start,int end){//接收用户取值范围 int i , j; for(i = start ; i &
所谓“筛选法”指的是“埃拉托色尼(Eratosthenes)筛法”。他是古希腊的著名数学家。他采取的方法是,
p91 #include <stdio.h> #include<math.h> int main ( ) { int m,i,k ; scanf("%d",&m)
这种方法的求素数的效率很高 #include <stdio.h> #include <stdlib.h> /*筛选法求素数,
今天突然想用Java实现如何用集合实现交集,并集和差集的运算了!主要是看Python语言的时候想起来的
这两种运算总是感觉有点迷糊,现在 拨开乌云见天日。 对于整型数a,b来说,取模运算或者求余运算的
今天,关于素数问题纠结了好久好久,倍感知识缺乏啊。因此,通过自己的了解和网上查阅资料,加上自
用java实现分数各种运算(加减乘除,求余,求幂,求两个数中的较大值,较小值) 1,要求 用户以分数形
上机内容:验证“求余”的语法规则 上机目的:学会用“撞错”理解语法要求的方法 * Copyright (c) 2
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号