1

Consider this challenge:

Given two numbers A and B, in how many ways you can select B distinct primes, where each of the primes should be less than or equal to A (<= 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?

senshin
  • 10,022
  • 7
  • 46
  • 59
Mohamed Ali JAMAOUI
  • 14,275
  • 14
  • 73
  • 117
  • 1
    BTW you could speed the search for primes up quite significantly if you used known `primes` in search for `is_prime`. See [this answer](http://stackoverflow.com/a/568618/223424). – 9000 Jan 25 '14 at 00:07
  • 1
    @9000 you mean [*this answer*](http://stackoverflow.com/a/10733621/849891)? It's a tweak of the code you linked to, and is 1.3x faster and takes *O(sqrt(n/log n))* extra space instead of *O(n)*, to produce *n* primes. – Will Ness Jan 25 '14 at 13:52

3 Answers3

1
for i in range(2,A):

should be 

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

because you have to consider all primes <= A.

Ionut Hulub
  • 6,180
  • 5
  • 26
  • 55
1

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)))
Nir Alfasi
  • 53,191
  • 11
  • 86
  • 129
0

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.

Scott Griffiths
  • 684
  • 6
  • 8