Что нужно сделать в этой задаче?

Question

[class_Human]

Не могу понять условие задачи:найти количество чисел меньших N, которые имеют простые делители X или Y.
Здесь надо разложить число на простые множители?

Comments

[Никита Егоров]

Инпут: 100, 5, 2
Оутпут: 9

Меньше 100 и делится на 5 и на 2 - 90, 80, 70, 60, 50, 40, 30, 20, 10.

[longclaps]

хех

[class_Human]

longclaps, это был совет от Дмитрия Анатольевича.

Answer 1

[Mercury13]

Если N=20, X=3, Y=5, то наш выход — 8.
3, 5, 6, 9, 10, 12, 15, 18.

Лобовое решение — пройти [2, N) и пересчитать нужные числа.

Идея умного решения. Если X и Y гарантированно простые, то эти самые числа повторяются с шагом X·Y.
3, 5, 6, 9, 10, 12, 15
18, 20, 21, 24, 25, 27, 30
А дальше думайте сами.

Answer 2

[Rsa97]

Не надо. Надо найти количество чисел, кратных X, добавить количество чисел кратных Y и вычесть количество чисел кратных X*Y. Задача решается без циклов, одной формулой.
N=20, X=3, Y=5
⌊19/3⌋ + ⌊19/5⌋ - ⌊19/15⌋ = 6 + 3 - 1 = 8

Answer 3

[Андрей]

$a = min([$x, $y]);
echo floor($n/$a)