Эх, не знаю я Python... Может, кто переведет?
Не актуально - см. ниже :)
Немного теории.
Все общие делители двух чисел определяются разложением НОД этих чисел на простые сомножители. Если НОД G
имеет разложение

то количество общих делителей может быть записано как

Число 5000 небольшое, так что факторизацию можно выполнять прямо по массиву простых чисел - их всего лишь 19, которые меньше квадратного корня из 5000.
По-моему, самый быстрый путь.
Код на C++:
#include <iostream>
using namespace std;
int gcd(int m, int n) // Поиск наибольшего общего делителя
{
while(m && n) if (m < n) n %= m; else m %= n;
return m + n;
}
// Все возможные простые делители чисел до 5000
int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 };
// Проверка числа на k общих делителей
bool cnt(int n, int m, int k)
{
int g = gcd(n,m); // НОД
int total = 1; // Количество общих делителей
// факторизуем НОД на простые сомножители; количество делителей -
// произведение их степеней, увеличенных на 1
for(int i = 0; g > 1 && i < size(primes); ++i)
{
int l = 0;
while(g%primes[i] == 0) { g /= primes[i]; ++l; }
total *= l+1;
}
return total == k;
}
int main(int argc, const char * argv[])
{
int n, k, count = 0;
cin >> n >> k;
// Перебор всех чисел
for(int m = 1; m < n; ++m)
if (cnt(n,m,k)) count++;
cout << count << endl;
}
Сравнение для 5000 2 с кодом @Psyperception по времени дает нефиксируемое :) время против 1.3 секунды...
С помощью напильника, Интернета и какой-то... перевел сам:
def gcd(m,n):
while m>0 and n>0:
if m < n :
n = n % m
else:
m = m % n
return m + n;
primes = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
def cnt(n,m,k):
g = gcd(n,m)
total = 1
for i in range(19):
if g <= 1: break
l = 0
while g%primes[i] == 0:
g = g // primes[i]
l = l + 1
total = total * (l+1)
return total == k
n = int(input('n: '))
k = int(input('k: '))
count = 0
for m in range(1,n):
if cnt(n,m,k) != 0: count = count + 1
print(count)
Должен заметить, что этот код на том же примере 5000 2
, что у @Psyperception выполняется за 1.3 секунды, у меня выполняется за 0.02 секунды - так, всего в 65 раз быстрее :)