Site Overlay

获取N以内的质数(Prime)

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

方法一:

/**
 * @Author Diuut
 * @Date 2019/8/15  20: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));
    }
}

本次运行耗时:3736

方法二

import java.util.ArrayList;
import java.util.List;
//检验一个数是不是素数,如果所有小于它的素数都不能将它整除,那么它就是素数
public class Test0814_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;
    }
}

本次运行耗时:375

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

方法三

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

/**
 * @Author Diuut
 * @Date 2019/8/15  23:31
 */
public class Test0814_5_showPrime {
    public static void main(String[] args) throws IOException {
        long start = System.currentTimeMillis();
        BufferedReader isr=new BufferedReader(new FileReader("Week07//prime2.txt"));
        String ss;
        while ((ss=isr.readLine())!=null) {
            System.out.println(ss);
        }
        isr.close();
        long end = System.currentTimeMillis();
        System.out.println("本次运行耗时:"+(end-start));
    }
}
本次运行耗时:171

更快的方法指的就是直接将需要的数据打包存好,不用消耗系统资源进行调用计算,就像之前试图优化站点访问速度的时候发现的一个插件 WP Super Cache ,原理就是将常用的动态页面直接缓存为静态页面,同redis缓存优化一样。用户访问的时候直接读取缓存好的静态页面,而不是发送请求,服务器再从数据库中读取,简单暴力没有技术含量,但却有效。

发表评论

邮箱地址不会被公开。 必填项已用*标注

A beliving heart is your magic My heart
Copyright © 2022 Diuut. All Rights Reserved. | Catch Vogue by Catch Themes | 蜀ICP备2021011635号-1 | magnet:?xt=urn:btih: