Найдите все натуральные числа, принадлежащие отрезку [101 000 000; 102 000 000], у которых ровно три различных чётных делителя (при этом количество нечётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
Ответ:
Заметим, что, поскольку необходимо найти чётные делители числа, можно не рассматривать нечётные числа из диапазона. Если число чётное, то
Приведём решение на языке Pascal.
var
count, i, j, k, sqrtI: longint;
begin
for i := 101000000 to 102000000 do if i mod 2 = 0 then begin
count := 1;
sqrtI := round(sqrt(i));
for j := 2 to sqrtI do begin
if i mod j = 0 then begin
if j mod 2 = 0 then count := count + 1;
k := i div j;
if k mod 2 = 0 then begin
count:=count + 1;
if j = k then count:=count - 1;
end;
if count > 3 then break;
end;
end;
if count = 3 then writeln(i);
end;
end.
В результате работы программа должна вывести следующее:
101075762
101417282
101588258
101645282
Примечание.
Заметим, что в данной программе условие j = k и соответствующая команда count = count − 1 не будут выполнены ни разу, поскольку если квадратный корень из числа четный, то это число делится
Приведем решение, которое предложил Данил.
Число имеет ровно три четных делителя, если оно имеет вид 2 · p2, где p — простое число. Следовательно, можно искать квадратный корень из числа, деленного
Приведем программу на языке Pascal, реализующую этот способ.
var
i,j,p,simple: longint;
begin
for i := 101000000 to 102000000 do if i mod 2 = 0 then begin
p := round(sqrt(i div 2));
if 2*p*p = i then begin
simple := 1;
for j := 2 to p - 1 do if p mod j = 0 then begin
simple := 0;
break;
end;
if simple = 1 then writeln(i);
end;
end;
end.
Приведем математическое обоснование данного способа.
Пусть разложение 
тогда количество делителей числа m равно 
В частности, четное число раскладывается на множители как 
где множители ai — нечетные числа. Тогда число имеет 
четных делителей и 
нечетных.
По условию задачи требуется, чтобы число имело 3 четных делителя. Число 3 можно представить в виде произведения единственным способом 1 · (2 + 1), следовательно, разложение искомого числа на простые множители должно иметь вид 2 · p2.
Примечание.
Заметим, что число 101576162 не является подходящим, поскольку имеет делители 2, 20158, 10078 и 101576162. Тем читателям, программы которых выводят данное число, рекомендуем обратить внимание на цикл перебора делителей числа. Перебор осуществляется обычно до значения квадратного корня из числа. Для
Приведём другое решение на языке Python.
for i in range(101000000, 102000000 + 1):
if i % 2 == 0:
count = 1
sqrtI = round(i ** 0.5)
for j in range(2, sqrtI + 1):
if i % j == 0:
if j % 2 == 0:
count += 1
k = i // j
if k % 2 == 0:
count += 1
if j == k:
count -= 1
if count > 3:
break
if count == 3:
print(i)
Приведём решение Кузнецова Александра на языке Python.
def Simple(n):
s = n % 2 + 1
for i in range(s+1, int(n**0.5)+1, s):
if n%i==0:
return False
return True
for i in range(101000000, 102000000+1, 2):
b = i / 2
if round(b**0.5)**2 == b and Simple(int(b**0.5)) == True:
print(i)
Приведём решение Юрия Красильникова на языке Python.
def prime(n):
k = 2
while k**2 <= n:
if n%k == 0:
return False
k += 1
return True
bot,top = 101000000,102000000
mp = int(top**0.5)+3
nums = [2*p**2 for p in range(3,mp,2) if prime(p) and bot <= 2*p**2 <= top]
for n in nums:
print(n)
Найдите все натуральные числа, принадлежащие отрезку [106 000 000; 107 000 000], у которых ровно три различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания.
Ответ:
Заметим, что, поскольку необходимо найти чётные делители числа, можно не рассматривать нечётные числа из диапазона. Если число чётное, то 1 четный делитель у него уже есть, поэтому переменную count будем объявлять со значением 1. Находя очередной делитель числа, будем проверять, является ли этот делитель чётным, и, если является, будем прибавлять к переменной count единицу. Также заметим, что у каждого делителя числа есть парный делитель — если он чётный, будем прибавлять к переменой count единицу. Также учтём то, что у числа может быть 2 одинаковых делителя (например, у числа 4 два одинаковых делителя — числа 2 и 2).
Приведём решение на языке Pascal.
var
count, i, j: longint;
sqrtI: real;
begin
for i := 106000000 to 107000000 do begin
count := 1;
sqrtI := round(sqrt(i));
if i mod 2 = 0 then begin
for j := 2 to round(sqrt(i)) do begin
if i mod j = 0 then
if j mod 2 = 0 then count := count + 1;
if i mod j = 0 then
if (i div j) mod 2 = 0 then count := count + 1;
if (j * j = i) and (j mod 2 = 0) then count := count - 1;
if count > 3 then break;
end;
end;
if count = 3 then writeln(i);
count := 1;
end;
end.
В результате работы программа должна вывести следующее:
106084178
106492418
106784498
106842962
Приведём решение на языке Python.
for i in range(106000000, 107000000 + 1):
count = 1
sqrtI = round(i ** 0.5)
if i % 2 == 0:
for j in range(2, sqrtI + 1):
if i % j == 0:
if j % 2 == 0:
count += 1
if i % j == 0:
if (i // j) % 2 == 0:
count += 1
if (j * j == i) and (j % 2 == 0):
count -= 1
if count > 3:
break
if count == 3:
print(i)
count = 1
Приведём решение Клима Орлова на языке Python.
def check(x):
k = 0
y = (x//2)
if y**0.5 == int(y**0.5):
z = y**0.5
for j in range(2,int(z**0.5)+1):
if z%j==0:
k += 1
break
if k == 0:
return True
else:
return False
for i in range(106000000,107000001,2):
if check(i) == True:
print(i)
Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40 000 000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания.
Ответ:
Решим задачу перебором. Находя очередной делитель числа, будем проверять, является ли этот делитель нечётным, и, если является, будем прибавлять
Приведём решение на языке Pascal.
var
count, i, j, k, sqrtI: longint;
begin
for i := 35000000 to 40000000 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.
В результате работы программа должна вывести следующее:
35819648
38950081
39037448
39337984
Приведем другое решение.
Число имеет ровно пять нечетных делителей, если оно имеет вид 2n · p4, где p — простое число, n — произвольное натуральное число. В этом случае нечетными делителями числа будут числа 1, p, p2, p3 и p4. Следовательно, можно искать корень четвертой степени из числа, деленного на максимально возможную степень двойки. Если этот корень четвертой степени является простым числом, то само число имеет ровно пять нечетных делителей.
Приведем программу на языке Pascal, реализующую этот способ.
var
simple, i, j, c, sqrtI: longint;
begin
for i := 35000000 to 40000000 do begin
c:=i;
while c mod 2 = 0 do begin
c:=c div 2;
end;
sqrtI := round(sqrt(c));
sqrtI:= round(sqrt(sqrtI));
if sqrtI * sqrtI * sqrtI * sqrtI = c then begin
simple:=1;
for j:=3 to round(sqrt(sqrtI)) do begin
if sqrtI mod j=0 then begin
simple:=0;
break;
end;
end;
if simple=1 then writeln(i);
end;
end;
end.
Приведем математическое обоснование данного способа.
Пусть разложение числа m на простые множители имеет вид тогда количество делителей В частности, четное число раскладывается на множители как где множители ai — нечетные числа. Тогда число имеет четных делителей и нечетных.
По условию задачи требуется, чтобы число имело
Примечание Никиты Степанова.
Второй способ решения будет давать неверный результат, если в заданном диапазоне есть число, являющееся степенью двойки. В этом случае получим sqrtI = c = 1, цикл проверки делимости числа не выполнится ни разу, и переменная simple останется
Приведём решение Владимира Лукьянчикова на языке Pascal.
uses school;
for var i := 35000000 to 40000000 do
if i.Divisors.Where(x -> x mod 2 = 1).Count = 5 then println(i);
Приведём решение Сергея Фефелова на языке Python.
def isPrime(n):
r = n%2 + 1
for i in range(r+1, int(n**0.5)+1, r):
if n % i==0: return False
return True
start, end = 35_000_000, 40_000_000
for i in range(start, end+1):
n = i
while n%2 == 0: n //= 2
q = round(n**0.25)
if n == q**4 and isPrime(q):
print(i)
Приведём решение Юрия Красильникова на языке Python.
def prime(n):
k = 2
while k**2 <= n:
if n%k == 0:
return False
k += 1
return True
bot,top = 35000000,40000000
mp = int(top**0.25)+3
m2 = len(bin(top))
nums = [p**4*2**m for p in range(3,mp,2) for m in range(m2) if prime(p) and bot <= p**4*2**m <= top]
for n in sorted(nums):
print(n)
Найдите все натуральные числа, принадлежащие отрезку [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<
Наверх