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

只是为了澄清,这不是一个功课问题:)

我想找到我正在建造的数学应用程序的素数并且遇到了Eratosthenes的Sieve方法.

我用Python编写了它的实现.但它非常慢.比方说,如果我想找到不到200万的所有素数.大约需要20分钟.(此时我停了下来).我怎样才能加快速度呢？

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

更新: 我最终对这段代码进行了分析,发现花了很多时间从列表中删除一个元素.考虑到它必须遍历整个列表(最坏情况)才能找到元素然后将其删除然后重新调整列表(可能还有一些副本继续？),这是相当容易理解的.无论如何,我把字典列表删掉了.我的新实施 -

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    for i in range(2, limitn): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)

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

INFINITE是这里的关键词.

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

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

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

我更喜欢非并发方法.

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

我试图通过取出子列表长度的复杂公式来进一步优化素数线程中的冠军解决方案.同一子序列的len()太慢,因为len很昂贵并且生成子序列很昂贵.这看起来稍微加快了功能,但我还是不能带走除法,尽管我只在条件语句中进行除法.当然,我可以尝试通过优化n的起始标记而不是n*n来简化长度计算...

我将division /整数除法//替换为与Python 3兼容

from __future__ import division

如果这个递推公式可以帮助加速numpy解决方案,我会很有趣,但我没有经验使用numpy.

如果你为代码启用了psyco,那么故事会变得完全不同,而且Atkins筛选代码变得比这种特殊的切片技术更快.

import cProfile

def rwh_primes1(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Returns  a list of primes < n """
    sieve = [True] * (n//2)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1,n/2) if sieve[i]]

def primes(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    # recurrence formula for length by amount1 and amount2 Tony Veijalainen 2010
    """ Returns  a list of primes < n """
    sieve = [True] * …

是否有一种有效的算法来按升序排列数n的因子而不进行排序？"有效"我的意思是:

1. 该算法通过从n的素数幂分解开始,避免了对除数的强力搜索.

2. 算法的运行时复杂度为O(d log 2 d)或更好,其中d是n的除数.

3. 算法的空间复杂度为O(d).

4. 该算法避免了排序操作.也就是说,这些因素是按顺序生成的,而不是按顺序生成并随后排序.尽管使用简单的递归方法进行枚举然后排序是O(d log 2 d),但是对于排序中涉及的所有存储器访问来说,存在非常难看的成本.

一个简单的例子是n = 360 =2³×3²×5,其中d = 24个因子:{1,2,3,4,5,6,8,9,10,12,15,18,20,24, 30,36,40,45,60,72,90,120,180,360}.

一个更严重的例子是n = 278282512406132373381723386382308832000 =2⁸×3⁴×5³×7²×11²×13²×17×19×23×29×31×37×41×43×47×53×59×61×67×71×73 ×79,其中d = 318504960因子(显然这里列出太多了!).顺便提一下,这个数字具有最大数量的因子,最多可达2 ^ 128.

我可以发誓几周前我看到了这种算法的描述,带有示例代码,但现在我似乎无法在任何地方找到它.它使用了一些魔术技巧,在每个素数因子的输出列表中维护一个祖先索引列表.(更新:我使用汉明数字混淆因子生成,其运算方式类似.)

更新

我最终在运行时使用O(d)的解决方案,具有极低的内存开销,可以就地创建O(d)输出,并且比我所知的任何其他方法都要快得多.我已经发布了这个解决方案作为答案,使用C源代码.它是另一个贡献者Will Ness在Haskell中提供的一个优化算法的优化简化版本.我选择了Will的答案作为公认的答案,因为它提供了一个非常优雅的解决方案,符合最初规定的所有要求.

我想使用我在网上找到并稍微改变的算法生成两个非常大的素数.

我在第5行得到这个错误:

Python OverflowError: cannot fit 'long' into an index=sized integer 

我的代码:

import math
def atkin(end):  
    if end < 2: return []  
    lng = ((end/2)-1+end%2)   
    **sieve = [True]*(lng+1)**  
    for i in range(int(math.sqrt(end)) >> 1):
        if not sieve[i]: continue  
        for j in range( (i*(i + 3) << 1) + 3, lng, (i << 1) + 3):  
            sieve[j] = False  
    primes = [2]  
    primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]])  
    return primes

我该如何修复错误？

如果您知道生成大质数的更好方法,那么这也会有所帮助.

我正在研究存储和查询大量项目的事件发生历史记录的解决方案.

这是一个简化的场景:我每天都会记录20万个路灯(标记为sl1到sl200000),显示灯是否在当天运行.灯泡在服务的时间长短只与特定日历日有关.

还为每个灯存储了其他信息,Python类的开头看起来像这样:

class Streetlamp(object):
    """Class for streetlamp record"""
    def __init__(self, **args):
        self.location = args['location']
        self.power = args['power']
        self.inservice = ???

我的py-foo不太好,我想避免在磁盘/内存存储上太贪心的解决方案.因此,使用(年,月,日)元组字典的解决方案可能是一种解决方案,但我希望能够获得更有效解决方案的指示.

记录可以存储为比特流,每个比特代表从1月1日开始的一年中的一天.因此,如果一盏灯在2010年的前三天运行,则记录可以是:

sl1000_up = dict('2010': '11100000000000...', '2011':'11111100100...')

跨年度搜索需要合并,闰年是一种特殊情况,而且我需要使用这种自行开发的解决方案来编码/解码.看起来不安静吧.加速位串位操作,如何在列表中查找缺失日期,以及使用位掩码查找数据间隙,我遇到了有趣的帖子.我还调查了python-bitstring并做了一些谷歌搜索,但似乎没有什么真的适合.

另外,我想搜索"差距"是可能的,例如"三天或更长时间不行动",并且标记的日期必须转换为真实的日历日期.

我会很感激想法或指向可能的解决方案.为了进一步增加细节,可能会感兴趣的是使用的后端数据库是ZODB,并且可以被腌制的纯Python对象是首选.

如何通过C++中的位操作找到素数？

可能重复:
在python中列出N下面所有素数的最快方法

虽然我已经编写了一个函数来查找n(primes(10) -> [2, 3, 5, 7])下的所有素数,但我很难找到一个快速查找前n个素数的方法.最快的方法是什么？