Python挑战:在给定范围内质数的独特组合

Question

考虑这个挑战：

给定两个数字A和B，可以通过几种方式选择B不同的素数，其中每个素数应小于或等于A（<= A）。由于数字可能很大，请提供您的答案mod 65537。

例如

如果A = 7和B = 2，则：
所有Primes <= 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)

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

Answer 1

ionut对包容性问题是正确的！
除此之外，您还应将NPK定义更改为：

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

Answer 2

for i in range(2,A):

应该是

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

因为您必须考虑所有素数＆lt; = a。

Answer 3

alfasin是正确的；问题是您选择素数的顺序无关紧要。因此，您想使用组合而不是置换。