算法 - 寻找素数，只许使用加法

Question

求一个算法，寻找小于某一预先给定的定值的全部素数，只许用加法（禁止减法、乘除法、乘方开方等复杂运算）

Answer 1

import re

r=re.compile(r'^(0{2,})?(\1)+
连数学都没用
ㄟ(▔ ,▔)ㄏ
)

def primes(n):
    return filter(lambda x: not r.match(''.zfill(x)), range(2, n))

连数学都没用

ㄟ(▔ ,▔)ㄏ

Answer 2

其实乘法是可以转化成加法的嘛， 所以下面这个简略的版本应该可以，希望有人可以给出更有意思的版本。

def filter_prime(n):
    if n < 2:
        return []
    options = [x for x in range(n)]
    # 1 不是素数，单独去除之
    options[1] = 0
    for i in options:
        if i:
            multi_i = i + i
            # 筛选出所有素数的整数倍（标记为 0）
            while multi_i <= n - 1:
                options[multi_i] = 0
                multi_i += i
     # 余下的所有没有被标记为 0 的，即为范围内的所有素数
     return [x for x in options if x]
            

Answer 3

哈哈，分享下某次脑洞大开时写的版本

function prime(max) {
    var primes = [];
    var primeMultiples = [];

    for (var i = 2; i < max; ++i) {
        var isPrime = true;
        for (var j = 0; j < primes.length; ++j) {
            if (i === primeMultiples[j]) {
                primeMultiples[j] += primes[j];
                isPrime = false;
            }
        }

        if (isPrime) {
            primes.push(i);
            primeMultiples.push(i + i);
        }
    }

    return primes;
}

console.log(prime(200000));