Найдите все натуральные числа, принадлежащие отрезку [45 000 000; 50 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
Ответ:
Решим задачу перебором. Находя очередной делитель числа, будем проверять, является ли этот делитель нечётным, и, если является, будем прибавлять
Приведём решение на языке Pascal.
var
count, i, j, k, sqrtI: longint;
begin
for i := 45000000 to 50000000 do begin
count := 0;
sqrtI := round(sqrt(i));
for j := 1 to sqrtI do begin
if i mod j = 0 then begin
if j mod 2 = 1 then count := count + 1;
k := i div j;
if k mod 2 = 1 then begin
count:=count + 1;
if j = k then count:=count - 1;
end;
end;
if count > 5 then break;
end;
if count = 5 then writeln(i);
end;
end.
В результате работы программа должна вывести следующее:
45212176
45265984
47458321
48469444
Примечание.
Другой способ решения, требующий меньше времени для работы программы, приведен в задаче 35483.
Приведём решение Владимира Столярова на языке Pascal.
## uses school;
for var i:=45000000 to 50000000 do
if i.Divisors.Count(n -> n mod 2=1)=5 then println(i)
Приведём решение Петра Полякова на языке Python.
def f1(x):
while x%2==0:
x=x//2
if (x**0.25) == int(x**0.25):return True
else:return False
def f(x):
k=2
deliteli=set()
if x%2!=0:deliteli.add(x)
deliteli.add(1)
while k*k<=x:
if x%k==0:
if k%2!=0:deliteli.add(k)
if x//k<x:
if (x//k)%2!=0:deliteli.add(x//k)
k=k+1
return sorted(deliteli)
start=45000000
end=50000000
numbers=[int(x) for x in range(start,end+1) if f1(x)==True]
for i in numbers:
if len(f(i))==5:
print(i)
Приведём решение Витаса Ремейкиса на языке Python.
primes = set()
def prime(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
for i in range(3, int(50000000**0.25) + 1):
if prime(i):
primes.add(i)
for i in range(45000000, 50000001):
p = i
while p % 2 == 0:
p //= 2
if int(p**0.25) in primes and (int(p**0.25))**4 == p:
print(i)
Приведём решение Юрия Лысакова на языке Python.
def kd(p):
a = []
z = 1
while p % 2 == 0:
p = p//2
if (p ** 0.25) == int(p ** 0.25):
for i in range(2,int(p**0.5)+1):
if p % i == 0:
if i % 2 == 1:
a.append(i)
if (p//i) % 2 == 1:
a.append(p//i)
if len(a) >= 4:
break
z = len(set(a)) + 1
if p % 2 == 1:
z += 1
return z
for i in range(45000000,50000001):
if kd(i) == 5:
print(i)
Приведём решение Юрия Красильникова на языке Python.
def isprime(n):
k = 2
while k**2 <= n:
if n%k==0: return False
k += 1
return True
# Число должно иметь вид p**4*2**n, где p - простое число, а n - целое неотрицательное.
a = [p**4*2**n for p in range(3,100,2) for n in range(0,30) if isprime(p)]
b = sorted([x for x in a if 45000000<=x<=50000000])
for x in b:
print(x)
Приведём решение Егора Чернецова на языке Python.
L,R=45_000_000,50_000_000
def P(n):return n>2 and all(n%i for i in range(3,int(n**.5)+1,2))
s={x for p in range(3,200,2) if P(p) for x in [p**4*(1<