返回顶部

收藏

java快速查找1~n之间的质数

更多
  1. 根据合数为多个质数之积判断
  2. 判断n是否为质数只要判断到sqrt(n)
  3. 在1~n中只要判断6m+1和6m+5,其余皆为合数。

[Java]代码

import java.util.ArrayList;

public class FindPrime {

    public static void main(String[] args) {
        double start  = System.currentTimeMillis() ; 
        ArrayList<Integer> PrimeArray = new ArrayList<Integer>();

        PrimeArray.add(2);
        PrimeArray.add(3);

        System.out.println("质数如下");
        System.out.println(2);
        System.out.println(3);

        int k=-1;
        for (int n =5; n <100000000; ) {
            int i;k++;
            for ( i = 0; i < PrimeArray.size(); i++) {
                if ( PrimeArray.get(i)*PrimeArray.get(i)>n)
                    {PrimeArray.add(n);
                    //System.out.println(n);
                    break;}
                else if (n % PrimeArray.get(i) == 0) {
                break;
                }       

            }
            if(k%2==0)
             n+=2;
            else
             n+=4;//if (k == PrimeArray.size())

        }

        double end  = System.currentTimeMillis() ; 
        System.out.println("程序运行时间为"+(end-start));
    }
}

标签:Java,质数

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. linux@linux.cn (linu 发表 2016-01-29 00:20:00 王垠:给 Java 说句公道话
  2. zhujiajun 发表 2016-02-04 14:43:56 Java注解全面解析
  3. 博主 发表 2016-02-03 02:41:00 在 JDK 9 中更简洁使用 try-with-resources 语句
  4. 刘莉莉 发表 2016-02-21 14:16:56 java并发库–锁
  5. neo 发表 2016-02-08 09:35:50 基于Protobuf的分布式高性能RPC框架——Navi-Pbrpc
  6. 童燕群 发表 2016-02-28 14:30:15 Jetty 8长连接上的又一个坑
  7. 博主 发表 2015-06-18 08:00:46 Javac和Java在CLI中的使用
  8. 刘莉莉 发表 2016-03-07 14:17:27 怎样打造一个DOM元素位置引擎 (一)
  9. 博主 发表 2013-10-26 00:00:00 Java Ten Object Oriented Design Principles
  10. 博主 发表 2016-03-13 10:53:22 混乱的 Java 日志体系
  11. admin 发表 2015-05-20 14:11:46 JavaFX实现android中的9patch功能
  12. 博主 发表 2015-11-26 05:52:15 json-lib反序列化精度丢失问题

发表评论