Среди целых чисел, принадлежащих числовому отрезку [156367;178945], найдите числа, которые представляют собой произведение двух различных простых делителей, не считая единицы и самого числа. Запишите в ответе через пробел количество таких чисел и минимальное их них.
Способ решения 1
# Функция для выявления простых чисел
def isSimple(n):
for d in range(2, int(n**0.5)+1):
if n % d == 0:
return False
return True
# Множество для подходящих чисел
nums = set()
# i и j — предполагаемые делители
for i in range(2, 100000):
for j in range(i+1, 100000):
# Если произведение уже выше дозволенного значения, то прерываем цикл
if i*j > 178945:
break
# Здесь проверяем, не меньше ли произведение, чем левая грань отрезка
if i*j >= 156367:
if isSimple(i) and isSimple(j):
nums.add(i*j)
print(len(nums), min(nums))
Способ решения 2
def prime(x): # функция проверки числа на простоту
return x > 1 and all(x % y for y in range(2,int(x**0.5)+1))
def divs(x): # функция, которая возвращает список делителей числа
d = set()
for i in range(2,int(x**0.5)+1):
if x % i == 0:
d.add(i)
d.add(x//i)
return sorted(d)
ans = []
for x in range(156367,178946):
d = [i for i in divs(x) if prime(i)] # cписок, в котором хранятся только простые делители числа
if len(d) == 2 and d[0]*d[1] == x: # если таких делителя ровно 2 и их произведение равно числу
ans += [x]
print(len(ans),min(ans))
Ответ: 4931 156367