Common divisors (the program does not work)
For a given positive integer n, find the number of integers x lying in the segment [1, n] such that the number of common divisors of n and x is equal to the given number k. For example, if k=1, then you need to find the number of numbers that are mutually simple with n that do not exceed it.
Input data In a single line of input data,two positive integers n and k (1≤n, k≤5000) are separated by a space.
Output data Output a single integer - the desired one quantity.
Examples
Input data 2 1 output data 1
Input data 12 2 output data 4
Input data 13 1 output data 12
Input data 720 6 output data 52
a = int(input())
b = int(input())
while a <= b:
m = 0
for i in range(1, a + 1):
if a % i == 0:
m += 1
if m >= n:
print(a, '-', m, end=' - ')
for i in range(1, a + 1):
if a % i == 0:
print(i, end=' ')
print()
a += 1
In general, the program does not go, if it is not difficult to write the code, please.
2 answers
Oh, I don't know Python... Can someone translate it?
Not relevant - see below :)
A little theory.
All common divisors of two numbers are determined by decomposing the nodes of these numbers into prime factors. If the node G has the decomposition
That number of common divisors can be written as
The number 5000 is small, so factorization can be performed directly on an array of prime numbers - there are only a few of them only 19, which are less than the square root of 5000.
In my opinion, the fastest way.
C++code:
#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;
}
Comparing for 5000 2 with the @Psyperception code in time gives an unfixable :) time vs 1.3 seconds...
With the help of a file, the Internet, and some kind of... translated by myself:
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)
I should note that this code in the same example 5000 2 that @Psyperception runs in 1.3 seconds, I run in 0.02 seconds - so, just 65 times faster :)
Try this way:
n = int(input('Введите число n: '))
k = int(input('Введите количество общих делителей k: '))
# эта функция возвращает количество всех общих
делителей
def all_deliteli(a,b):
n = 0
for i in range(1, min(a, b) + 1):
if a % i == b % i == 0:
n += 1
return n
count_chisel = 0 # счетчик
""" Тут мы начинаем циклом проходить от 1 до указанного числа n.
Проверяем общее число делителей двух чисел: 1 и 1, потом
1 и 2, 1 и 3 и т.д """
for x in range(1, n + 1):
all_gcd = all_deliteli(x, n)
if all_gcd == k: # Если число делителей совпадает с нашим
указанным числом k, то мы увеличиваем счетчик
count_chisel += 1 # вот тут
print(count_chisel)