技术栈

主页 > 前端开发 >

你是如何求素数?

素数:质数,又称素数,是只能被1或者自己整除的自然数。
题目要求:求出 100 以内所有素数

1. 以前遇到这样的题目都是用一个 for 循环然后求出所有符合要求的数。

代码:

function isPrime(num) {
    if (num < 2) {
        return false;
    }
    for (let i = 2; i < num; i++) {
        if (num % i === 0) {
            return false;

        }
    }
    return true
}

let prime = [];
for (let i = 0; i < 100; i++) {
    if (isPrime(i)) {
        prime.push(i)
    }
}
console.log(prime)

输出:

[ 2,  3,  5,  7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89, 97 ]

2. 今天在网上看到了一个用正则表达式判断是否是素数,然后求出素数的代码,仔细研究收获很大。

代码:

function prime(max) {
    var re = new RegExp('^(11+?)\1+$'),
        str = '1',
        i = 1,
        ret = [];
    while (max > i++)
        re.test(str += '1') || ret.push(i);
    return ret;
}
var arr = prime(100);
console.log(arr);

输出:

[ 2,  3,  5,  7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97 ]

仔细研究,可以发现这个方法可算是有点技术含量,很巧了,我简单分析一下我的理解:

首先是前面的正则表达式:

 '^(11+?)\1+$'
“^” —— 正则匹配字符串开始位置;
"(11+?)"—— ? 代表重复前面“11+”  0 次或 1 次,“+” 是重复前面的 1 次或多次。
“1+”——剩余的字串的1的个数要是前面字串1个数的整数倍;
“$”——结束匹配。

举栗子:
比如 3 是 111,它不符合重复 “11" 次数,它也不符合重复 “1111” 次数,所以就是匹配失败,返回 false;
比如 9 是 111111111,它重复了 “111” 的整数倍,所以符合匹配,返回 ture;

然后是一个 while 循环:

while (max>i++){
  re.test(str += '1') || ret.push(i);
}

这里真的是很厉害了,利用了 “||” 运算符的特性,如果前面判断正确,运算符后面就不执行,如果前面判断错误,就执行运算符后面的语句,这是我第一次遇到这样的语句,为了证明我的想法是正确的,我在 push 后面加了一个输出语句:

re.test(str += '1') || ret.push(i,function () {
        console.log(re.test(str += '1'), i)
    });

运行结果:

[ 2,  [Function],  3,  [Function],  5,  [Function],  7,  [Function],  11,  [Function],  13,  [Function],  17,  [Function],  19,  [Function],  23,  [Function],  29,  [Function],  31,  [Function],  37,  [Function],  41,  [Function],  43,  [Function],  47,  [Function],  53,  [Function],  59,  [Function],  61,  [Function],  67,  [Function],  71,  [Function],  73,  [Function],  79,  [Function],  83,  [Function],  89,  [Function],  97,  [Function] ]

可以看到只有素数进行了后面的 push 操作,大神不愧是大神想法这么牛逼,送上膝盖 ,跪拜,跪拜。。。

责任编辑:admin  二维码分享:
本文标签: strreprimepush11Function
点击我更换图片

评论列表