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

实现此功能的最佳方式是什么:

ArrayList generatePrimes(int n)

此函数生成第一个n素数(编辑:where n>1),因此generatePrimes(5)将返回ArrayListwith {2, 3, 5, 7, 11}.(我在C#中这样做,但我很高兴Java实现 - 或任何其他类似的语言(所以不是Haskell)).

我知道怎么写这个函数,但是当我昨晚做到这一点时,它并没有像我希望的那样结束.这是我想出的:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime …

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

INFINITE是这里的关键词.

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

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

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

我更喜欢非并发方法.

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

可能重复:
如何确定一个数字是否是正则表达式的素数？

此页面声称此正则表达式发现非素数(并通过反例:素数):

/^1?$|^(11+?)\1+$/

这怎么找到素数？

只想要一些关于我的素数发生器的反馈.例如,它是否正常,它是否用于很多资源等.它不使用库,它相当简单,它反映了我目前的编程技巧状态,所以不要因为我想学习而退缩.

def prime_gen(n):

    primes = [2]
    a = 2 

    while a < n:

        counter = 0 

        for i in primes:
            if a % i == 0:
                counter += 1

        if counter == 0:
            primes.append(a)
        else:
            counter = 0

        a = a + 1

    print primes

我需要在Python中使用生成器生成素数.这是我的代码:

def genPrimes():
    yield 2
    x=2
    while True:
        x+=1
        for p in genPrimes():
            if (x%p)==0:
                break
        else:
            yield x

我有一个RuntimeError:当我运行它时,在第二个prime.next()之后超出了最大递归深度.