Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например,
Например, в диапазоне [5; 16] ровно три различных нетривиальных делителя имеет
16 8
Ответ:
Если решать задачу перебором — программа будет существенно неэффективна по времени. Заметим, что у каждого делителя числа имеется пара, например, пары делителей числа 16 будут выглядеть так:
Приведём решение на языке Pascal.
var
numDel, i, j: longint;
maxDel: longint;
sqrtI: real;
begin
for i := 123456789 to 223456789 do begin
sqrtI := sqrt(i);
numDel := 0;
if (round(sqrtI) = sqrtI) then begin
maxDel := 1;
for j := 2 to round(sqrtI) - 1 do begin
if (i mod j = 0) then begin
if (maxDel = 1) then maxDel := i div j;
numDel := numDel + 2;
end;
end;
if numDel = 2 then writeln(i, ' ', maxDel);
end;
end;
end.
В результате работы программа должна вывести следующее:
131079601 1225043
141158161 1295029
163047361 1442897
Примечание.
Другой способ решения представлен в задаче 33104.
Приведём решение на языке Python.
maxi = 0
for i in range(123456789, 223456790):
sqrti = i**0.5
numdel = 0
if round(sqrti) == sqrti:
maxdel = 1
for j in range(2, round(sqrti) - 1):
if i % j == 0:
if maxdel == 1: maxdel = i // j
numdel += 2
if numdel == 2: print(i, maxdel)
Приведём другое решение на языке Python.
import math
i = int(math.sqrt(123456789))+1
j=i*i
while j <= 223456789:
n = 0
d = 0
for k in range(2,i):
if j%k == 0:
n = n+1
d = j//k
if n>1: break
if n == 1:
print(j,d)
i = i+1
j = i*i
Приведём решение Станислава Степанова на языке Python.
import math
a = 123456789
b = 223456789
for i in range(int(a ** 0.25), int(b ** 0.25) + 1):
for j in range(2, int(i ** 0.5) + 1):
if not i % j:
break
else:
if i > 1:
print(i ** 4, i ** 3)
Приведём решение Михаила Глинского на языке Python.
for x in range(123456789,223456789+1 ):
if (x**0.5) == round(x**0.5):
m = set()
for i in range(2,round(x**0.5)+1):
if x%i==0:
m.add(i)
m.add(x//i)
if len(m)>3: break
if len(m) == 3:
print(x,max(m))
Приведём решение Бориса Савельева на языке Python.
for k in range (round(123456789**0.5),round(223456789*0.5+1)):
a = []
i = k**2
if k*k == i:
for j in range (2,k+1):
if i%j==0:
a.append(j)
if j != (i//j):
a.append(i//j)
if len(a) == 3:
print(i,max(a))
Приведём решение Юрия Красильникова на языке Python.
# Число, имеющее 5 различных делителей (т. е. 3 нетривиальных делителя),
# должно иметь вид p**4, где p - простое число.
# Делители: 1, p, p**2, p**3, p**4
def prostoe(n):
k = 2
while k*k <= n:
if n%k == 0:
return False
k += 1
return True
for n in range(int(123456789**0.25),int(223456789**0.25)+1):
if prostoe(n): print(n**4,n**3)