Задача по программированию. Вероятность и теория чисел

[Jigan]

Вычислить вероятность того что два случайным образом выбранных числа из отрезка $[1, \Bbb N]$ будут взаимно простыми. $1 \leq {\Bbb N}\leq 10^6$.

Решение в лоб не проходит по времени (ограничение 1 секунда). Даже не знаю с какой стороны подступиться.

[Doil-byle]

Ну, можно взять большее число $n$, факторизовать его, вычислить функцию Эйлера и поделить её значение на $n-1$. Хотя это в ряд ли быстро. Функцию Эйлера можно вычислить так: $n = \prod_{i=1}^k p_i^{\alpha_i},$ тогда $\varphi(n) = \prod_{i=1}^k p_i^{\alpha_i - 1} \left( p_i - 1 \right)$. Ну, вообще, это решение не привязано к программированию.
Зы.
Забыл учесть, что случайные числа могут оказаться равными. Ну, тут очевидно, что делать.

[ИСН]

Это Вы хрень какую-то говорите (или я чего-то не понял), а надо по формуле включений-исключений.

[Doil-byle]

Ну у меня сделано в предположении того, что мы можем найти большее число.

[ИСН]

Большее чем что? И как оно связано с задачей?

[Doil-byle]

Большее из двух чисел.

[ИСН]

Из каких двух? Случайно выбранных? Так оно любым может быть.

[Doil-byle]

Ну да, поэтому в предположении того, что известно, какое больше. То есть второе случайно выбирается из множества чисел, меньших первого. Но можно рассмотреть три несовместных события: $a >b, a<b, a=b $ и использовать формулу полной вероятности.

[ИСН]

Так даже если известно, положим, что первое больше - оно всё равно любым может быть.

[Doil-byle]

Да, может быть любым, но разложение на множители для него всё равно будет, просто неизвестно, какое именно. Формулу-то записать всё равно можно. Хотя, конечно, нехорошо, что вероятность выражается через случайную величину.

[Sonic86]

При больших $n$ искомая вероятность ведет себя как $\frac{6}{\pi ^2}+O(\frac{\ln n}{n+1})$ - этим можно пользоваться для самопроверки.

[Александрович]

Doil-byle в сообщении #549578 писал(а):

Хотя, конечно, нехорошо, что вероятность выражается через случайную величину.

Так не должно быть.

[Jigan]

Спасибо метод включений--исключений вкатил:)