Ionut is correct about the inclusive issue!
In addition to that, you should change nPk definition to:
def nPk(n,k):
return int( factorial(n)/(factorial(n- k) * factorial(k)))
Question
Consider this challenge:
Given two numbers
A
andB
, in how many ways you can selectB
distinct primes, where each of the primes should be less than or equal toA
(<= A
). Since the number can be large, provide your answer mod 65537.
For example
If A = 7
and B = 2
, then:
All primes <= A
are {2, 3, 5, 7}
, and the answer will be 6
: {2, 3} {2, 5} {2, 7} {3, 5} {3, 7} {5, 7}
I have created this solution:
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)
But, I am not getting the right answer! What am I missing here?
Solution
Ionut is correct about the inclusive issue!
In addition to that, you should change nPk definition to:
def nPk(n,k):
return int( factorial(n)/(factorial(n- k) * factorial(k)))
OTHER TIPS
for i in range(2,A):
should be
for i in range(2, A+1):
because you have to consider all primes <= A.
alfasin is correct; the issue is that the order in which you choose the primes doesn't matter. Thus you want to use a combination rather than a permutation.