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

bf
  • 8k

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

回复
阅读 3.3k
3 个回答
import re

r=re.compile(r'^(0{2,})?(\1)+$')

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

连数学都没用

ㄟ(▔ ,▔)ㄏ

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

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]
            

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

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));
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏