相关疑难解决方法(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方法以及素数公式的频率？

我更喜欢非并发方法.

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

我使用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 …

我无法理解这段代码:

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

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

我写了一个函数,使用流无限期地生成质数(维基百科:Erastothenes的增量筛).它返回一个流,但它也在内部合并素数倍流以标记即将到来的复合.如果我自己这样说,这个定义简洁,实用,优雅且易于理解:

def primes(): Stream[Int] = {
  def merge(a: Stream[Int], b: Stream[Int]): Stream[Int] = {
    def next = a.head min b.head
    Stream.cons(next, merge(if (a.head == next) a.tail else a,
                            if (b.head == next) b.tail else b))
  }
  def test(n: Int, compositeStream: Stream[Int]): Stream[Int] = {
    if (n == compositeStream.head) test(n+1, compositeStream.tail)
    else Stream.cons(n, test(n+1, merge(compositeStream, Stream.from(n*n, n))))
  }
  test(2, Stream.from(4, 2))
}

但是,当我尝试生成第1000个素数时,我得到了"java.lang.OutOfMemoryError:超出GC开销限制".

我有一个替代解决方案,它在primes上返回一个迭代器,并在内部使用元组的优先级队列(multiple,prime用于生成多个)来标记即将到来的复合.它运行良好,但它需要大约两倍的代码,我基本上不得不从头重新开始:

import scala.collection.mutable.PriorityQueue
def primes(): Iterator[Int] = {
  // Tuple (composite, prime) is used to generate …

我的问题直接来自CS圈子网站.这是对底部的最后一个问题这一页称为"引为起飞".基本纲要是他们想要一个1,000,001长度的列表,其中如果索引是素数,则每个项目的索引为True,而如果它不是素数,则每个项目的索引为False.

因此,例如,isPrime [13]是True.isPrime [14]是假的.

列表'isPrime'的第一点看起来像:

isPrime = [False, False, True, True, False, True, False, True, False, False, ...]

我的问题是他们有7秒的时间限制.我有一个下面的工作代码,数字较小,为101,用于调试目的.当我将它提升到所需的1,000,001列表长度时,它需要的时间太长,几分钟后我终于杀死了程序.这是我的工作(长度为101),代码非常慢:

n = 101
c = 2
isPrime = [False,False]
for i in range(2,n):
    isPrime.append(i)

def ifInt(isPrime):
    for item in isPrime:
        if type(item) == int:
            return item
for d in range(2,n):
    if c != None:
        for i in range(c,n,c):
            isPrime[i] = False
        isPrime[c] = True
        c = ifInt(isPrime)

然后是我在这里找到的这个.它有一个更快的运行时间,但只输出一个素数列表,而不是一个n长度列表,list [n]返回True表示素数,否则返回false.

我不确定这个第二位代码是否真的能够在7秒内创建长度为1,000,001的素数列表,但这是我在研究中找到的最相关的东西.

def primes_sieve1(limit):
limitn = limit+1 …

如何在Python中生成此列表？a(n)不是素数+ a(k),k <n的形式.

这是oeis http://oeis.org/A025043上的列表

它分为0,1,9,10,25,34,35,49,55,85,91,100,115,121.

我已经尝试过大胆的方式,结果并不顺利.现在我正在寻找一种复杂的解决方案,比如Eratosthenes的Sieve for primes.粗体方式需要迭代每个素数,并且对于素数的每次迭代,迭代序列中已经花费很长时间的每个数.

这个表是由聪明的人生成的:http://oeis.org/A025043/b025043.txt 他们要么使用了大量的计算能力,要么使用了复杂的算法,我正在寻找它.

为了解释这个序列是什么,每个不存在的数字可以表示为该序列中的素数和数字之和.例如,8 = 7(素数)+ 1(按顺序),54 = 53(素数)+1(按顺序),等等.

我正在尝试制作一个不错的Java程序,从1到N生成素数(主要用于Project Euler问题).

目前,我的算法如下:

初始化一个布尔数组(如果N足够大则初始化为bitarray),因此它们都是假的,并且存储了一组用于存储素数的整数.

设置一个整数,s等于最低素数,(即2)

s是<= sqrt(N)

在数组/位阵列中将s的所有倍数(从s ^ 2开始)设置为true.

找到array/bitarray中的下一个最小索引,该索引为false,将其用作s的新值.

ENDWHILE.

遍历数组/位阵列,对于每个假的值,将相应的索引放在primes数组中.

现在,我试过跳过不是6k + 1或6k + 5形式的数字,但这只能让我加速~2倍,而我看到程序运行的速度比我的速度快(虽然非常复杂)代码),例如这里的那个

我该怎么做才能改善？

编辑:好的,这是我的实际代码(对于1E7的N):

int l = 10000000, n = 2, sqrt = (int) Math.sqrt(l);
boolean[] nums = new boolean[l + 1];
int[] primes = new int[664579];

while(n <= sqrt){
    for(int i = 2 * n; i <= l; nums[i] = true, i += n);
    for(n++; nums[n]; n++);
}

for(int i = 2, k = 0; i < nums.length; i++) if(!nums[i]) primes[k++] …

在找到第10,001个素数时,我的内存耗尽.

object Euler0007 {
  def from(n: Int): Stream[Int] = n #:: from(n + 1)
  def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.filter(_ % s.head != 0))
  def primes = sieve(from(2))
  def main(args: Array[String]): Unit = {
    println(primes(10001))
  }
}

这是因为在每次"迭代"(这是这个上下文中的正确术语吗？)之后primes,我增加要调用的函数堆栈以使下一个元素一个接一个？

我在网上找到的一个解决方案是不使用迭代解决方案(我想避免进入函数式编程/惯用scala),这就是问题7(问题7):

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

从我所看到的,这不会导致这种类似递归的方式.这是一个很好的方法吗,或者你知道更好的方法吗？

我正在寻找一种生成素数的算法.我发现罗伯特威廉汉克斯完成了以下一个.它比其他算法更有效,更好,但我无法理解它背后的数学.

def primes(n):
    """ Returns  a list of primes < n """
    lis = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if lis[i]:
            lis[i*i::2*i]=[False]*int((n-i*i-1)/(2*i)+1)
    return [2] + [i for i in range(3,n,2) if lis[i]]

Trues值数组和最终素数数组之间的关系是什么？