这是我能提出的最佳算法.
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方法以及素数公式的频率？
我更喜欢非并发方法.
感谢您阅读(和写作;))!
我一直在努力解决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 …我无法理解这段代码:
let
sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]
有人可以为我分手吗？我知道它有递归,但这就是问题我无法理解这个例子中的递归是如何工作的.
是否有一个库函数可以枚举Python中的素数(按顺序)？
我发现这个问题最快的方法列出N以下的所有素数但是我宁愿使用别人的可靠库而不是我自己的库.我很乐意这样做import math; for n in math.primes:
只想要一些关于我的素数发生器的反馈.例如,它是否正常,它是否用于很多资源等.它不使用库,它相当简单,它反映了我目前的编程技巧状态,所以不要因为我想学习而退缩.
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中创建素数生成器,这只是一个有趣的练习.
以下代码按预期工作,但速度太慢:
primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
for i in primes(10):
print i,
所以我试图通过检查j和k的平方根来做到这一点:
primes = lambda q: (i for i in xrange(1,q) if i not in [j*k for j in xrange(1,int(round(math.sqrt(i)+1))) for k in xrange(1,int(round(math.sqrt(i)+1)))])
for i in primes(10):
print i,
但它输出: 2 3 5 6 7 8
所以我的指数j和k肯定有问题,但我没有线索.
我的代码粘贴在下面.当我运行这个程序时,它继续计算.我正在使用旧的Turbo C++编译器.这样的程序需要多长时间才能执行？我等了大约5分钟,但没有任何输出.
/*The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
*/
#include<stdio.h>
#include<conio.h>
#define TWO_MILLION 2*1000*1000
int IsPrime(long unsigned int num);
int main()
{
long unsigned int i,sum=0;
clrscr();
for(i=2;i<TWO_MILLION;i++)
{
if(IsPrime(i))
sum+=i;
}
gotoxy(25,25);
printf("%ld",sum);
getch();
return 0;
}
int IsPrime(long unsigned int num)
{
int flag=1;
long unsigned int i;
for(i=2;i<num;i++)
{
if(num%i==0)
{
flag=0;
break;
}
}
return …我目前正在尝试为 Kattis 问题实现埃拉托斯特尼筛的一个版本，但是，我遇到了一些内存限制，我的实现无法通过。
这是问题陈述的链接。简而言之，这个问题要求我首先返回小于或等于n 的素数数量，然后求解一定数量的查询，判断数字i是否为素数。内存使用量限制为 50 MB，并且只能使用 python 标准库（无 numpy 等）。内存限制是我陷入困境的地方。
到目前为止，这是我的代码：
import sys
def sieve_of_eratosthenes(xs, n):
count = len(xs) + 1
p = 3 # start at three
index = 0
while p*p < n:
for i in range(index + p, len(xs), p):
if xs[i]:
xs[i] = 0
count -= 1
temp_index = index
for i in range(index + 1, len(xs)):
if xs[i]:
p = xs[i]
temp_index += 1
break
temp_index += 1 …