相关疑难解决方法(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

我想打印前10000个素数.任何人都可以给我最有效的代码吗？澄清:

1. 如果你的代码在n> 10000时效率低下并不重要.
2. 代码的大小无关紧要.
3. 您不能以任何方式对值进行硬编码.

我正在尝试在Wikipedia Link中实现Atkin的Sieve算法,如下所示:

阿特金筛子

到目前为止我尝试过的是Python中的代码:

import math
is_prime = list()
limit = 100
for i in range(5,limit):
    is_prime.append(False)

for x in range(1,int(math.sqrt(limit))+1):
    for y in range(1,int(math.sqrt(limit))+1):
        n = 4*x**2 + y**2

        if n<=limit and (n%12==1 or n%12==5):
            # print "1st if"
            is_prime[n] = not is_prime[n]
        n = 3*x**2+y**2
        if n<= limit and n%12==7:
            # print "Second if"
            is_prime[n] = not is_prime[n]
        n = 3*x**2 - y**2
        if x>y and n<=limit and n%12==11:
            # print "third if"
            is_prime[n] = not is_prime[n]

for …

我知道可以实施Eratosthenes筛,以便在没有上限(分段筛)的情况下连续找到质数.

我的问题是,阿特金/伯恩斯坦的筛子能否以同样的方式实施？

相关问题:C#:如何制作Atkin增量扫描

然而,相关问题只有一个答案,即"所有筛子都不可能",这显然是不正确的.

我有一个很长的字符串，几乎有一兆字节长，我需要将其写入文本文件。常规的

file = open("file.txt","w")
file.write(string)
file.close()

可以，但是太慢了，有什么办法可以写得更快吗？

我正在尝试将几百万位数字写入文本文件，该数字约为math.factorial(67867957)

这是分析中显示的内容：

    203 function calls (198 primitive calls) in 0.001 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 re.py:217(compile)
        1    0.000    0.000    0.000    0.000 re.py:273(_compile)
        1    0.000    0.000    0.000    0.000 sre_compile.py:172(_compile_charset)
        1    0.000    0.000    0.000    0.000 sre_compile.py:201(_optimize_charset)
        4    0.000    0.000    0.000    0.000 sre_compile.py:25(_identityfunction)
      3/1    0.000    0.000    0.000    0.000 sre_compile.py:33(_compile)
        1    0.000    0.000    0.000    0.000 sre_compile.py:341(_compile_info)
        2    0.000    0.000 …