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

末蓝、 2022-05-31 04:19 244阅读 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 条评论，244人围观）

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

相关阅读

相关 Mybatis使用大于等于或小于等于进行比较

前言今天有一个需求，把之前的判断逻辑进行修改，之前我是用大于(>)小于(<)进行对比的，但是今天让改成大于等于(>=)和小于等于(<=)进行比较本来以为是一个很简单

今天药忘吃喽~/ 2023年09月24日 19:56/ 0 赞/ 53 阅读

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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