ms_shnits

Количество чисел из [30001; 70000], у которых больше 17 различных делителей

Apr 17th, 2021
739
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #python 3.6.9
  2.  
  3. # Назовём натуральное число подходящим, если у него больше 17 различных делителей (включая единицу и само число).
  4. # Определите количество подходящих чисел, принадлежащих отрезку [30 001; 70 000], а также наименьшее из таких чисел.
  5. # В ответе запишите два целых числа: сначала количество, затем наименьшее число.
  6. # ( https://otvet.mail.ru/question/224587128 )
  7.  
  8.  
  9.  
  10. # задаём границы интервала, в котором будем искать числа, имеющие больше 17 различных делителей
  11. lo, hi = 35001, 70000
  12.  
  13.  
  14.  
  15. # ищем простые числа, котороые могут быть собственными делителями чисел из интересующего нас интервала
  16. Primes = [0, 0] + list(range(2, round(hi**.5)+1))
  17.  
  18. i = 0
  19. for i in range(2, len(Primes)):
  20.     if Primes[i]:
  21.         for j in range(i*2, len(Primes), i):
  22.             Primes[j] = 0
  23.  
  24. Primes = list(filter(lambda x : x, Primes))
  25. # закончили искать простые числа
  26.  
  27.  
  28.  
  29. # функция, возвращаюшщая все простые собственные делители заданного числа
  30. # (использует список простых чисел, найденный на предыдущем этапе)
  31. def Factorization(N, topLevel = True) :
  32.     result = []
  33.     if N in Primes :
  34.         return result if topLevel else [N]
  35.     for p in Primes:
  36.         if not(N%p) :
  37.             result += [p] + Factorization(N//p, False)
  38.             break
  39.     return [list(filter(lambda y: y==x, result)) for x in set(result)] if topLevel else result
  40.  
  41.  
  42.  
  43. # функция, подсчитывающая количество различных делителей числа, включая само это число и единицу
  44. def DivizorsCount(primeDivizors):
  45.     if primeDivizors == []:
  46.         return 2
  47.     result = 1
  48.     for d in primeDivizors:
  49.         result *= len(d) + 1
  50.     return result
  51.  
  52.  
  53.  
  54. # (вспомогательная функция, инкрементирующая составной счётчик - потребуется в следующей функции)
  55. def incCounter(counter, counterMax):
  56.     i = 0
  57.     while True:
  58.         counter[i] += 1
  59.         if counter[i] <= counterMax[i]:
  60.             return True
  61.         counter[i] = 0
  62.         i += 1
  63.         if i >= len(counterMax):
  64.             return False
  65.  
  66.  
  67.  
  68. # функция, возвращающая все различные делители числа, включая само это число и единицу
  69. def GetDivizors(N, primeDivizors):
  70.     if primeDivizors == []:
  71.         return [1, N]
  72.     counter, counterMax = [0]*len(primeDivizors), [len(d) for d in primeDivizors]
  73.     result = []
  74.     while True:
  75.         divizor = 1
  76.         for i in range(len(counter)):
  77.             divizor *= primeDivizors[i][0]**counter[i]
  78.         result.append(divizor)
  79.         if not(incCounter(counter, counterMax)):
  80.             break
  81.     return result
  82.  
  83.  
  84.  
  85. # подсчитываем в интересующем нас интервале количество чисел, имеющих больше 17 различных делителей, включая само это число и единицу,
  86. # а также определяем минимальное из таких чисел
  87. count, minN = 0, None
  88. for N in range(lo, hi+1):
  89.     primeDivizors = Factorization(N)
  90.     if DivizorsCount(primeDivizors) > 17:
  91.         count += 1
  92.         if minN is None: minN = (N, primeDivizors)
  93.            
  94. # выводим результат
  95. print(count, minN[0])
  96. print("делители числа %d:" %(minN[0]), sorted(GetDivizors(*minN)))
  97.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×