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

制作一个简单的筛子很容易:

for (int i=2; i<=N; i++){
    if (sieve[i]==0){
        cout << i << " is prime" << endl;
        for (int j = i; j<=N; j+=i){
            sieve[j]=1;
        }
    }
    cout << i << " has " << sieve[i] << " distinct prime factors\n";
}

但是当N非常大并且我无法在内存中保存那种数组时呢？我已经查找了分段筛选方法,它们似乎涉及到找到素数直到sqrt(N),但我不明白它是如何工作的.如果N非常大(例如10 ^ 18)怎么办？

我正在为Diffie-Hellman类型密钥生成2048位安全素数,p使得p和(p-1)/ 2都是素数.

我可以在p和(p-1)/ 2上使用几次Rabin-Miller迭代,并且仍然对加密密钥有信心吗？在我做过的研究中,我已经听到了1024位普通素数的6到64次迭代的所有内容,所以我在这一点上有点困惑.一旦确定,如果您正在生成一个安全的素数而不是普通素数,那么数字是否会改变？

计算时间非常宝贵,所以这是一个实际的问题 - 我基本上想知道如何找到尽可能少的测试数量,同时保持非常有保障的安全性.

我正在尝试使用布尔函数打印从1到100的所有素数.

以下是我正在运行的代码.

for n in range(1,101):
status = True
if n < 2:
    status = False
else:
    for i in range(2,n):
        if n % i == 0:
            status = False

    if status:
        print(n, '', sep=',', end='')

但是当我把代码放在函数和运行模块中时,shell上没有任何打印.我做错了什么？

is_prime():
    for n in range(1,101):
        status = True
        if n < 2:
            status = False
        else:
            for i in range(2,n):
                if n % i == 0:
                    status = False
        return status

if is_prime():    
    print(n, '', sep=',', end='')

以下是该计划的输出.如何防止最后一个逗号打印？
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,