是否有一种有效的算法来确定随机选择的大整数不能被某个集合中的任何整数整除的概率？

Question

给定一组 10 个整数 $A = a_1, a_2, \cdots a_{10}$, ，有没有一种有效的算法可以告诉我随机选择的整数之间的概率是多少 $1$ 和 $10^{10}$ 是 不是 可以被该集合的任何成员整除。

我知道包含-排除原则可以用来解决这个问题，但我不知道如何实现它以便它有效地工作。

笔记:当我说“高效”时，我指的是多项式时间，但我并不完全确定在这种情况下什么才算多项式时间，因为两个变量都是固定的。

Answer 1

让 $\mathbf x$ 是范围内的随机数 $1,\l点,N$, ， 然后让 $E_i$ 表示事件 $\mathbf x$ 可以整除 $a_i$. 。您感兴趣的是没有任何事件发生的概率 $E_1,\l点,E_m$ 发生（在你的情况下， 百万美元 = 10 美元）。使用包含-排除原理，这可以简化为计算以下形式的事件的概率 $E_{i_1} \land \cdots \land E_{i_k}$, ， 那是， $\mathbf x$ 可以被所有整除 $a_{i_1},\ldots,a_{i_k}$. 。自从一个 $\mathbf x$ 能被一堆数字整除当且仅当它能被它们的 LCM 整除时，就足以确定以下概率 $\mathbf x$ 可以整除 $a$.

之中 $1,\l点,N$, ，可除以的数字 $a$ 是$$ a，2a，3a， ldots， lfloor n/a rfloor a，$$总共 $\lfloor 不适用 floor$ 数字。因此概率是 $\mathbf x$ 可以整除 $a$ 正是$$ frac { lfloor n/a rfloor} {n}。$$