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

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

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

我一直在努力解决Clojure中的Project Euler问题,以便变得更好,而且我已经遇到了几次素数.我的问题是它只是花了太长时间.我希望有人可以帮我找到一种以Clojure-y方式做到这一点的有效方法.

当我拳头做到这一点时,我粗暴地强迫它.这很容易做到.但是计算10001个素数在Xeon 2.33GHz上用了2分钟,对规则来说太长了,一般来说太长了.这是算法:

(defn next-prime-slow
    "Find the next prime number, checking against our already existing list"
    ([sofar guess]
        (if (not-any? #(zero? (mod guess %)) sofar)
            guess                         ; Then we have a prime
            (recur sofar (+ guess 2)))))  ; Try again                               

(defn find-primes-slow
    "Finds prime numbers, slowly"
    ([]
        (find-primes-slow 10001 [2 3]))   ; How many we need, initial prime seeds
    ([needed sofar]
        (if (<= needed (count sofar))
            sofar                         ; Found enough, we're done
            (recur needed (concat sofar [(next-prime-slow …

我使用Sieve of Eratosthenes和Python 3.1 编写了一个素数生成器.代码在ideone.com上以0.32秒正确且优雅地运行,以生成高达1,000,000的素数.

# from bitstring import BitString

def prime_numbers(limit=1000000):
    '''Prime number generator. Yields the series
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...    
    using Sieve of Eratosthenes.
    '''
    yield 2
    sub_limit = int(limit**0.5) 
    flags = [False, False] + [True] * (limit - 2)   
#     flags = BitString(limit)
    # Step through all the odd numbers
    for i in range(3, limit, 2):       
        if flags[i] is False:
#        if flags[i] is True:
            continue …

我对纯粹功能性F#中的eratosthenes筛子的实施很感兴趣.我对实际筛子的实现感兴趣,而不是真正的筛子的天真功能实现,所以不是这样的:

let rec PseudoSieve list =
    match list with
    | hd::tl -> hd :: (PseudoSieve <| List.filter (fun x -> x % hd <> 0) tl)
    | [] -> []

上面的第二个链接简要描述了一个需要使用多图的算法,据我所知,这在F#中是不可用的.给出的Haskell实现使用了一个支持insertWith方法的映射,我在F#功能映射中没有看到它.

有没有人知道将给定的Haskell映射代码转换为F#的方法,或者可能知道替代实现方法或筛选算法哪些有效且更适合功能实现或F#？

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

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

我无法理解这段代码:

let
  sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]

有人可以为我分手吗？我知道它有递归,但这就是问题我无法理解这个例子中的递归是如何工作的.

我最近了解到Data.Function.fix,现在我想在任何地方应用它.例如,每当我看到递归函数时,我想" fix"它.所以基本上我的问题是我应该在何时何地使用它.

为了使它更具体:

1)假设我有以下代码用于分解n:

f n = f' n primes
  where
    f' n (p:ps) = ...
    -- if p^2<=n: returns (p,k):f' (n `div` p^k) ps for k = maximum power of p in n
    -- if n<=1: returns []
    -- otherwise: returns [(n,1)]

如果我改写它fix,我会获得一些东西吗？失去什么？有可能,通过重写一个显式的递归到fix-version我会解决,反之亦然会创建一个堆栈溢出？

2)处理列表时,有几种解决方案:递归/修复,foldr/foldl/foldl',可能还有别的东西.关于何时使用每种方法,是否有任何一般指导/建议？例如,您是否会使用foldr无限的素数列表重写上面的代码？

可能还有其他重要问题没有在这里讨论.欢迎任何与使用相关的其他评论fix.

生成素数是一个玩具问题,我经常不时尝试,特别是在尝试新的编程语言,平台或风格时.

我正在考虑尝试使用Hadoop(Map Reduce)编写素数生成算法或素数测试算法.

我想我会发布这个问题,以获得提示,参考,算法,方法.

虽然我的主要兴趣是基于Map Reduce的算法,但我不介意查看新的Hadoop编程模型或者例如查看使用PiCloud

我在Prime数字生成中似乎有一些有趣的问题:这里,这里和这里,但没有任何与Parallel方法相关的问题引起了我的注意.

提前致谢.