[Java] 获取N以内的质数(Prime)

本帖最后由 Diuut 于 2019-9-12 16:43 编辑

只要仔细想一想就能写出来的代码，但是得出结果容易，得出结果花费的时间就不一样了。为了对比出效果，N取100000。

方法一

[Java] 纯文本查看 复制代码

/**
 * @Author Diuut
 * @Date 2019/8/15  21:54
 */
public class Test0814_1_Prime {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int j;
        for(int i = 2;i<=100000;i++) // 1不是素数，所以直接从2开始循环
        {
            j = 2;
            while (i % j != 0)
                j++; // 测试2至i的数字是否能被i整除，如不能就自加
            if (j == i) // 当有被整除的数字时，判断它是不是自身
                System.out.println(i); // 如果是就打印出数字
        }
        long end = System.currentTimeMillis();
        System.out.println("本次运行耗时:"+(end-start));
    }
}

[Java] 纯文本查看 复制代码

//本次运行耗时:3736

方法二

[Java] 纯文本查看 复制代码

import java.util.ArrayList;
import java.util.List;
//检验一个数是不是素数，如果所有小于它的素数都不能将它整除，那么它就是素数
public class Test0815_2_Prime {
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        List<Integer> primes=getPrimes(100000);
 
        for(int i=0;i<primes.size();i++) {
            Integer prime=primes.get(i);
            System.out.println(prime+" ");
        }
        long end = System.currentTimeMillis();
        System.out.println("本次运行耗时："+(end-start));
    }
 
    /*
     * 求n以内的所有素数
     *
     */
    private static List<Integer> getPrimes(int n){
        List<Integer> result =new ArrayList<Integer>();
        result.add(2);//第一个素数先放入
        for(int i=3;i<=n;i+=2) {  //遍历，减少循环次数，步长为2
            if(!divisble(i,result)) {  //判断是否有素数能被整除
                result.add(i);     //如果不能整除，加入列表List
            }
        }

        return result;  //返回列表list
    }
 
    /*
     * 判断n能否能被整除
     *
     */
    private static boolean divisble(int n,List<Integer> primes) {
        for(Integer prime:primes) {  //遍历列表List
            if(n % prime == 0) {
                return true;
            }
            if(prime>=Math.sqrt(n))   //如果超过平方根，还没找到整除，退出循环
                break;
        }
        return false;
    }
}
//定理：若n（n∈N）不能被小于根号n的任一质数整除，则n为质数。

[Java] 纯文本查看 复制代码

//本次运行耗时：375

结果非常明显，不同的写法，得到的结果都是一样的，但是花费的时间却是天壤之别。一组代码差1秒，一整个项目下来区别就不一样了。 (下面还有更快的方法。

方法三

[Java] 纯文本查看 复制代码

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
 
/**
 * @Author Diuut
 * @Date 2019/8/15  23:31
 */
public class Test0815_5_showPrime {
    public static void main(String[] args) throws IOException {
        long start = System.currentTimeMillis();
        BufferedReader isr=new BufferedReader(new FileReader("Week07//prime2.txt"));
        //项目下存放着10W内的质数的txt文件，每行存一个。
        //更好的情况下会在数据库中绑定id主键，这样就更方便查询。
        String ss;
        while ((ss=isr.readLine())!=null) {
            System.out.println(ss);
        }
        isr.close();
        long end = System.currentTimeMillis();
        System.out.println("本次运行耗时："+(end-start));
    }
}

[Java] 纯文本查看 复制代码

本次运行耗时：171

更快的方法指的就是直接将需要的数据打包存好，不用消耗系统资源进行调用计算，就像之前试图优化站点访问速度的时候发现的一个插件 WP Super Cache ，原理就是将常用的动态页面直接缓存为静态页面，同redis缓存优化一样，用户访问的时候直接读取缓存好的静态页面，而不是发送请求，服务器再从数据库中读取，简单暴力没有技术含量，但却有效。
原博客地址：http://diuut.xyz/%E5%AD%A6%E4%B9%A0/492/%E8%8E%B7%E5%8F%96n%E4%BB%A5%E5%86%85%E7%9A%84%E8%B4%A8%E6%95%B0prime/

帐号		自动登录	找回密码
密码			加入黑马

[Java] 获取N以内的质数(Prime)

0 个回复