Python的挑战：在给定范围内的素数的不同组合

鉴于两个数字A和B，你可以有多少种选择B不同的素数，其中每个素数的应小于或等于A（<= A）。由于数量可能很大，提供你的答案MOD 65537

例如

如果A = 7和B = 2，则：
所有质数<= A是{2, 3, 5, 7}，答案将是6：{2, 3} {2, 5} {2, 7} {3, 5} {3, 7} {5, 7}

我已经创建了这个解决方案：

from math import factorial 
from math import fmod 

def nPk(n,k): 
    return int(factorial(n)/factorial(n- k)) 

def is_prime(a): 
    for i in range(2,a): 
     if a % i ==0: 
      return False 
    return True 

def distinct_primes(A): 
    primes = [] 
    for i in range(2,A): 
     if is_prime(i): 
      primes.append(i) 
    return len(primes) 

def fct(A, B): 
    return nPk(distinct_primes(A),B) 

#print fct(59,5)% 65537 
print fmod(fct(69,8), 65537)

但是，我没有得到正确的答案！我在这里错过了什么？

来源

2014-01-24 MedAli

顺便说一句，如果你使用已知的'primes'来搜索'is_prime'，你可以非常显着地加快搜索质数。看[这个答案]（http://stackoverflow.com/a/568618/223424）。 – 9000

谢谢，不错的提示！ – MedAli

@ 9000你的意思是[*这个答案*]（http://stackoverflow.com/a/10733621/849891）？这是对你链接的代码的调整，速度快1.3倍，并且需要* O（sqrt（n/log n））*额外的空间而不是* O（n）*来产生* n *素数。 –

约努茨是关于包容性的问题，正确的！
除此之外，你应该改变NPK定义：

def nPk(n,k): 
    return int(factorial(n)/(factorial(n- k) * factorial(k)))

来源

2014-01-24 23:56:38 alfasin

编辑的函数在某些情况下失败，例如n = 334和k = 25我看不出原因，请您再看一下 – MedAli

for i in range(2,A):

应该

for i in range(2, A+1):

，因为你必须考虑所有的素数< = A.

来源

2014-01-24 23:47:57

alfasin是正确的;问题在于您选择素数的顺序无关紧要。因此你想要使用组合而不是排列。

来源

2014-01-25 01:33:52

Python的挑战：在给定范围内的素数的不同组合

回答

相关问题