1

По заданным числам a и b найдите среди всех чисел отрезка [a,b] такое число, которое имеет наибольшее количество делителей. Если таких чисел несколько, то выведите наибольшее.

Входные данные В единственной строке задано два целых числа: a,b (1≤a≤b≤5000) — границы отрезка поиска.

Выходные данные Выведите одно целое число — число с наибольшим количеством делителей среди чисел отрезка [a,b]. Если таких чисел несколько, то выведите наибольшее.

Примеры

входные данные 1 10 выходные данные 10

входные данные 3 4 выходные данные 4

входные данные 3 6 выходные данные 6

def num_div(n):
        r=2
        i=2
        while (i*i<=n):
                if n%i==0:
                        r+=1
                if n//i != i:
                        r+=1
                i+=1   
        return r
def task(a,b):
        xmax=0
        dmax=0
        x=b
        while(x>=a):
                nd=num_div(x)
                if nd>dmax:
                        dmax=nd
                        xmax=x
                x-=1   
        return xmax
[a,b]=map(int,input().split(' '))       
print(task(a,b))

Не проходит на 11 тесте. Исправьте, пожалуйста, что не правильно в этой программе.

3
  • 1
    num_div работает неправильно. Она должна находить степени при простых делителях и перемножать их, прибавив к каждой единицу. Например, число 28 = 2 * 2 * 7 = 2 ^ 2 * 7 ^ 1. Количество его делителей = (2 + 1) * (1 + 1)
    – extrn
    12 янв 2020 в 15:10
  • 1
    @Мария Лоскутова Почему Вы за всё время не приняли ни одного ответа?
    – MBo
    12 янв 2020 в 18:42
  • А подскажите, пожалуйста, как это в программе исправить
    – wargas
    13 янв 2020 в 10:23

3 ответа 3

2

Попробуйте if nd>dmax: заменить на >= -вам же нужно наибольшее значение при одинаковых количествах делителей.

А еще просьба (ко всем) - когда даете такие задачи, давайте сразу URL, где задача задана и где тестирующая система...

1

Генерируем за O(5000) все простые числа от 2 до 5000, за O(log(n)) получаем кол-во делителей числа n. Итоговая асимптотика: O(5000 + n log (n)). Пройдет даже для ограничений 1 <= a, b <= 10^5.

N = int(5e3);
lp = [0] * (N + 1)
pr = []
# Решето Эратосфена с линейным времени работы
def gen_primes():
    for i in range(2, N + 1):
        if lp[i] == 0:
            lp[i] = i;
            pr.append(i);
        j = 0
        while j < len(pr) and pr[j] <= lp[i] and i * pr[j] <= N:
            lp[i * pr[j]] = pr[j]
            j+=1
def count_divisors(a):
    ans = 1
    last_prime = lp[a]
    cur = 0
    while (a > 1) :
        if (lp[a] != last_prime):
            ans *= (cur + 1)
            cur = 0
            last_prime = lp[a]
        cur+=1
        a //= lp[a]
        if (lp[a] == 1):
            break
    return ans * (cur + 1)
gen_primes()
a, b = map(int, input().split())
mx = 2
mx_num = 2
for i in range(a, b + 1):
    r1 = count_divisors(i)
    if r1 >= mx:
        mx_num = i
        mx = r1
print(mx_num)
1
  • На 4 тесте не проходит(
    – wargas
    15 янв 2020 в 15:47
0

Hayk Sardaryan

import time
startTime = time.time()
a,b=map(int,input().split(' '))
if a<b:
    a,b=b,a
c,d=a,b
x,y=[],[]
delitel=2
while a>1:
    if a%delitel==0:
        x.append(delitel)
        a//=delitel
    else:
        delitel+=1
while b>1:
    if b%delitel==0:
        y.append(delitel)
        b//=delitel
    else:
        delitel+=1
if len(x)>=len(y):
    print(c)
else:
    print(d)
print ('The script took {0} second !'.format(time.time() - startTime))

На 2 тесте проходит

1
  • На 2 тесте не проходит и времени очень много программа требует
    – wargas
    13 янв 2020 в 10:21

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.