算法性能比较（一）——找出小于等于n的所有素数

末蓝、 2022-05-31 04:19 225阅读 0赞

算法性能比较系列文章主要用于记录笔者刷题时自己写的算法与最佳算法之间的性能比较。

计算素数一般会用下面这样的算法：

function isPrimeNum(num) { 
        for (let i = 2; i <= Math.sqrt(num); i++) {
            if (num%i === 0){
                return false;
            }
        }
        return true;
    }
    
    function count(max) { 
        let num = 2;
        let primeList = [];
        let start = (new Date()).valueOf();
        while (num <= max) {
            if (isPrimeNum(num)) {
                primeList.push(num);
            }
            num++;
        }
        let end = (new Date()).valueOf();
        console.log("num is " + primeList.length + " used time is " + (end - start));
    }
    
    count(10000000);

在笔者的电脑上用时如下（浏览器版本：chrome 64.0.3282.140（正式版本） （64 位））：  
![执行用时][20180206214202682]

然后来瞻仰一下大佬的算法：

function countFast(max) { 
        var array = new Array(max);
        let primeList = [];
        let start = (new Date()).valueOf();
        for (var j = 2; j < Math.sqrt(max); j++) {
            for (var i = j * j; i < max; i += j) {
                array[i] = true;
            }
        }
        for (var k = 2; k < max; k++) {
            if (!array[k]) primeList.push(k);
        }
        let end = (new Date()).valueOf();
        console.log("num is " + primeList.length + " used time is " + (end - start));
    }
    countFast(10000000);

在笔者的电脑上用时如下：  
![执行用时][20180206214356528]

第一种算法的时间主要消耗在了isPrimeNum函数里，里面包含了大量的无用计算。

两种思路对应的算法，性能相差了15倍，只能说脑子是个好东西，你值得拥有。

[20180206214202682]: /images/20220531/ff40d021839d478282623cf032335f0a.png
[20180206214356528]: /images/20220531/c00e2bf029d34ad299d8b500da8f322f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，225人围观）

还没有评论，来说两句吧...

相关阅读

相关 Eratosthenes筛选法求小于N的所有素数个数

求出1~N范围中所有的素数，在leetcode中做过这个题目，我想从对每个1~N进行一次遍历，每个数判断一次是否是素数。判断一个数是否是素数的复杂度本身也是挺高的，再进行一

叁歲伎倆/ 2022年07月12日 03:22/ 0 赞/ 230 阅读

相关 Eratosthenes筛选法求小于N的所有素数个数

求出1~N范围中所有的素数，在leetcode中做过这个题目，我想从对每个1~N进行一次遍历，每个数判断一次是否是素数。判断一个数是否是素数的复杂度本身也是挺高的，再进行一

港控/mmm°/ 2022年07月12日 03:22/ 0 赞/ 212 阅读

相关 java 找出小于数字N的所有素数

代码如下所示： package test3; import java.util.Scanner; / 找出小于数字N的

悠悠/ 2022年06月17日 12:15/ 0 赞/ 218 阅读

相关 [素数]:编写函数,求出小于或等于lim的所有素数，并放在aa数组中，函数返回所求的素数个数。

//编写函数,求出小于或等于lim的所有素数，并放在aa数组中，函数返回所求的素数个数。 \include<stdio.h> \define MAX 100

今天药忘吃喽~/ 2022年06月11日 04:15/ 0 赞/ 182 阅读

相关快速求小于N的所有素数

首先，贴上实现的源代码： // // main.cpp // testC++1 // // Created by fei dou

我会带着你远行/ 2022年06月08日 01:07/ 0 赞/ 236 阅读

相关算法性能比较（二）——找出特殊的奇偶数

原题简单描述如下：给定一个数组，数组包含至少3个元素，所有元素均为整数，且所有元素符合：只包含一个偶数其余全部为奇数或只包含一个奇数其余全部为偶数，找出这个单独的偶数/奇

悠悠/ 2022年05月31日 09:19/ 0 赞/ 178 阅读

相关算法性能比较（一）——找出小于等于n的所有素数

算法性能比较系列文章主要用于记录笔者刷题时自己写的算法与最佳算法之间的性能比较。计算素数一般会用下面这样的算法： function isPrimeNum(num)

末蓝、/ 2022年05月31日 04:19/ 0 赞/ 226 阅读

相关输入一个自然数n，求小于等于n的素数之和？

问题描述：输入一个自然数n，求小于等于n的素数之和；例如：样例输入：2 样例输出：2。解题思路：（1）什么是素数：素

痛定思痛。/ 2022年05月17日 11:38/ 0 赞/ 278 阅读

相关求出1-N中的所有素数，不连N算。

import java.util.Scanner; public class Main \{ public static void main(String\[\] ar

矫情吗；*/ 2022年04月22日 11:24/ 0 赞/ 220 阅读

相关找出数字x的秩（小于或等于x的值的数目）

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] /\\ \ 功能：假设你正在读取一串整数。每隔一段时

淩亂°似流年/ 2022年01月13日 14:13/ 0 赞/ 208 阅读