Решение:
Это будет работать долгое время
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
|
for i in range(35000000, 40000000 + 1): if i % 2 != 0: k = 2 else: k = 1 d = 2 while d * d < i: if i % d == 0: if d % 2 != 0: k += 1 if (i//d) % 2 != 0: k += 1 if k > 5: break d += 1 if d * d == i and d % 2 != 0: k += 1 if k == 5: print(i) |
Вот более быстрый метод: если есть простое число, 4-я степень которого равна самому числу, то это число имеет ровно 5 нечетных делителей.
Разложим искомое число на простые. Так как в дальнейшем нас будут интересовать нечётные делители, степень двойки выписана отдельно:
n = 2^k0 * p1^k1 * p2^k2 * ... * pi*ki
,
где k0
— целое неотрицательное, k1, ..., ki
— натуральные, p1, ..., pi
— различные нечётные простые.
Любой делитель n
конструируется как произведение простых из разложения выше. Сколько нечётных делителей мы можем сконструировать? (k1 + 1)(k2 + 1) ... (ki + 1)
. Это прозведение может быть равно пяти только если у числа ровно один нечётный простой делитель, который возводится в четвёртую степень.
Искомое число должно иметь вид 2^k * p^4
, где k
— целое неотрицательное, p
— нечетное простое. Сами нечётные делители тогда имеют вид 1, p, pp, ppp, pppp
.
|
def isprime(n): d = 2 while d * d <= n: if n % d == 0: return False d += 1 return True for i in range(35000000, 40000000 + 1): a = i while a % 2 == 0: a = a // 2 if (a ** 0.25) == int(a ** 0.25): if isprime(a ** 0.25): print(i) |
35819648
38950081
39037448
39337984
Ответ:
35819648
38950081
39037448
39337984