6

我正在尝试在一行 Python 中创建素数生成器，作为一个有趣的练习。

以下代码按预期工作，但速度太慢：

primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
for i in primes(10):
   print i,

所以我试图通过只检查 j 和 k 的平方根来做到这一点：

primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,int(round(math.sqrt(i)+1))) for k in xrange(1,int(round(math.sqrt(i)+1)))])
for i in primes(10):
   print i,

但它输出：2 3 5 6 7 8

所以我的索引 j 和 k 一定有问题，但我不知道。

4

12 回答 12

13

这不是埃拉托色尼的筛子，尽管它看起来是。事实上，情况要糟糕得多。Sieve 是寻找素数的最佳算法。

见http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

编辑：我已将https://stackoverflow.com/a/9302299/711085修改为单线（最初它不是真正的筛子，但现在......可能......）：

reduce( (lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r), 
        range(2,N), set(range(2,N)))

演示：

>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}

可悲的是，我认为虽然这在函数式编程语言中会很有效，但由于非持久（共享状态和不可变）数据结构，它在 python 中可能效率不高，并且 python 中的任何筛子都需要使用突变来实现可比性能。如果我们非常想的话，我们仍然可以把它塞进一个单列中。但首先...

普通筛：

>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
...     if table[i]:
...         for mult in range(i**2,N,i):
...             table[mult] = False
... 
>>> primes = [p for p in table if p][1:]
>>> primes
[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]

我们现在可以在同一行定义和调用匿名函数，以及[...].__setitem__进行内联突变的技巧，以及返回... and foo时评估的技巧：...foo

>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

继续惊恐地畏缩，单行扩展（奇怪的漂亮，因为你几乎可以直接翻译控制流，但对一切都是可怕的滥用）：

lambda N:
    (lambda table: 
        [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] 
            for i in range(2,int(N**0.5)+1) if table[i]] 
        and [p for p in table if p][1:]
    )(list(range(N)))

在我的机器上，这个单线变异版本在 10 8左右放弃了，而原始变异版本在 10 9左右放弃了，内存不足（奇怪）。

原版在 10 7reduce放弃。所以也许它毕竟不是那么低效（至少对于您可以在计算机上处​​理的数字）。

编辑2似乎您可以更简洁地滥用副作用：

reduce( (lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
                     if (x in r) else r), 
        range(2,N), set(range(2,N)))

它在 10 8左右放弃，与单线变异版本相同。

编辑3：这以O(N)经验复杂度运行，而没有difference_update它以O(n^2.2) 复杂度运行。

将减少的范围限制为上限的 sqrt，并仅使用赔率，两者都会导致额外的加速（相应地2倍和1.6 倍）：

reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
                     if (x in r) else r), 
        range(3, int((N+1)**0.5+1), 2),
        set([2] + range(3,N,2)))
于 2012-05-17T16:52:00.307 回答
3

您不能只检查直到平方根的数字乘积来测试素数。看 8 - 8 的平方根是 2.8，所以它永远不会尝试 4 * 2。（事实上，唯一不会被视为素数的数字是平方数）。

ETA：与其尝试 j 和 k 的所有可能组合，不如检查 i 是否可以被每个 j 整除（使用i % j == 0）直到 j 的平方根？这既需要更少的代码，也更有效（尽管它仍然不如Eratosthenes 的筛子高效）。

于 2012-05-17T16:46:36.647 回答
3

这就是你想要的：

def primes (q) :
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,j+1)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,j+1)])

 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,min(j+1,i/j+1))])

在 Haskell 中，范围是包容性的，所以primes(542)是

[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..n-1]]]  --  25.66s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..j]]]    --  15.30s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..j]]]    --   6.00s
                                                                      --   0.79s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..min j (n`div`j)]]]

实际上，1*x == x因此不需要1作为乘数，因此它应该是

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..min j (n`div`j)]]]

仅需 0.59 秒。或者，在 Python 中，

def primes (q) :
 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(2,i/2+1) for k in xrange(2,min(j+1,i/j+1))])

更新：出于某种原因，min j ...至少在 Haskell 中没有太大区别。所以表达式变得简单

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..n`div`j]]]
于 2012-05-19T10:10:50.003 回答
3

怎么样：

def primes(x):
  return [i for i in range(2,x) if 0 not in [i%j for j in range(2,i)]]
于 2017-07-23T04:56:02.817 回答
1

使用推导

[x for x in range(4, 1000) if all(x % y != 0 for y in range(2, int(math.sqrt(x)) + 1))]
于 2019-04-28T09:46:12.773 回答
1

虽然这里还有其他很好的答案，但我想包括我的版本。

n = 1000
primes = [candidate for candidate in range(1, n) if candidate not in [x * mult for x in range(2,n // 2 + 1) for mult in range(2,n//x)]]

这具有 O(n**2) 的运行时间。

于 2020-01-09T22:23:36.503 回答
0 
def isPrime(n):
    return all(n % d for d in range(2, int(n**.5)+1))

primes = set(n for n in range(2, 100) if isPrime(n))

如果需要，可以将其压缩为一行：

primes = set(n for n in range(2, 100) if all(n % d for d in range(2,int(n**.5)+1)))

Whereall()确保没有任何值是False (或0)；在这种情况下，确保我们正在测试的数字以下的数字都不是因子，在这种情况下，数字是素数。

我们检查直到数字平方根的所有因子以提高效率：如果 sqrt(n) 以下的数字不是因子，则 sqrt(n) 之上的数字都不是因子，因为因子总是成对出现。

于 2019-10-31T21:46:40.980 回答
0

这是一个单行代码：

print((lambda n:[i for i in range(2, n) if ["A7A" for j in range(2, i) if i%j==0]==[]])(100))
于 2020-06-30T14:18:05.010 回答
0

这是另一种方式，它不是单行但更有效。积极的一面是，每次您只检查以前找到的素数而不是查看 range(n) 中的所有值：

def prime(n):
    pm_list = [2]
    for i in range(3,n+1):
        pm_arr = np.array(pm_list)
        if any(i // pm_arr == i / pm_arr) == False:
            pm_list.append(i)
    return pm_list
于 2021-01-27T18:48:56.777 回答
0

这是一个基于 Eratosthenes 筛子的 oneliner。

primes = lambda N: (N>1)*[2]+[p for s in [[1]*(N+1)] for p in range(3,N+1,2) if s[p] and not s.__setitem__(slice(p,None,p),N//p*[0])]

它在我的笔记本电脑上在 0.097 秒内生成多达 1,000,000 个素数。

对于高达 10^8 的素数：11.6 秒，

对于高达 10^9 的素数：169.3 秒（2.8 分钟）

对于高达 10^10 的素数：似乎内存不足（IDLE shell 退出）

于 2021-01-28T17:43:10.653 回答
0

以下代码应打印低于值“限制”的所有数字的列表。

primes = lambda limit: [num for num in range(2, limit) if num > 1 and (num == 2 or num % 2 != 0) and all(num % divisor != 0 for divisor in range(3, int(num ** 0.5) + 1, 2))]

print(primes(30))
于 2021-12-27T16:55:54.057 回答
-1

我的代码是（对于范围（2,50）中的数字）：

import operator

[len(x) for x in list(map(lambda x: [operator.mod(len(range(1,x)), z) for z in range(1,x)], [item for item in range(2,50)])) if x.count(0) == 2]
于 2021-05-09T18:24:04.573 回答