相关疑难解决方法(0)

这是我能提出的最佳算法.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

可以做得更快吗？

此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

这不是作业,我只是好奇.

INFINITE是这里的关键词.

我希望在primes()中使用它作为p.我相信这是Haskell中的内置函数.

所以,答案不能像"Just do a Sieve"那样天真.

首先,您不知道将消耗多少连续素数.好吧,假设你可以一次编制100个.您是否会使用相同的Sieve方法以及素数公式的频率？

我更喜欢非并发方法.

感谢您阅读(和写作;))!

请问有人请告诉我这段代码我做错了什么？无论如何,它只是打印'计数'.我只想要一个非常简单的素数发生器(没什么特别的).

import math

def main():
    count = 3
    one = 1
    while one == 1:
        for x in range(2, int(math.sqrt(count) + 1)):
            if count % x == 0: 
                continue
            if count % x != 0:
                print count

        count += 1

我是编程世界的新手.我只是在python中编写这段代码来生成N个素数.用户应输入N的值,即打印出的素数总数.我写了这段代码,但它没有抛出所需的输出.相反,它打印素数直到第N个数字.例如:用户输入N = 7的值.所需输出:2,3,5,7,11,13,19实际输出:2,3,5,7

好心提醒.

i=1
x = int(input("Enter the number:"))
for k in range (1, (x+1), 1):
    c=0
    for j in range (1, (i+1), 1):
        a = i%j
        if (a==0):
            c = c+1

    if (c==2):
          print (i)
    else:
          k = k-1

    i=i+1

我有一个素数生成器,我很好奇看到有多小和我有多快可以让素数生成器基于优化等等:

from math import sqrt
def p(n):  
  if n < 2: return []  
  s = [True]*(((n/2)-1+n%2)+1)  
  for i in range(int(sqrt(n)) >> 1):  
    if not s[i]: continue  
    for j in range( (i**i+(3*i) << 1) + 3, ((n/2)-1+n%2), (i<<1)+3): s[j] = False   
    q = [2]; q.extend([(i<<1) + 3 for i in range(((n/2)-1+n%2)) if s[i]]); return len(q), q  
print p(input())

发电机很棒!它速度超快,可以随意试用.但是,如果您输入的数字大于10 ^ 9或10 ^ 10(我认为),它将从内存错误中崩溃.我无法弄清楚如何扩展它使用的内存,以便它可以占用所需的内存.任何建议将不胜感激!

我的问题与此问题非常相似,但这是Python,而不是C.

编辑:这是我尝试运行10 ^ 9时获得的与内存相关的回溯之一.

python prime.py
1000000000
Traceback (most recent call last):
  File "prime.py", line 9, …