找出两个随机选取的整数(从n个整数)得到相对素数的概率

Question

我遇到了发现这种概率的问题,我的第一次尝试是提出以下算法:我正在计算相对素数的对数.

int rel = 0
int total = n * (n - 1) / 2
for i in [1, n)
    for j in [i+1, n)
        if gcd(i, j) == 1
            ++rel;
return rel / total

这是O(n ^ 2).

这是我尝试降低复杂性:

观察(1): 1是相对素数,[2, n]因此n - 1对是微不足道的.

观察(2): 2对于该范围内的偶数不是相对素数,[4, n]因此剩余的奇数是2的相对素数,因此

 #Relatively prime pairs = (n / 2) if n is even 

                         = (n / 2 - 1) if n is odd.

所以我的改进算法将是:

int total = n * (n - 1) / 2
int rel = 0
if (n % 2) // n is odd
    rel = (n - 1) + n / 2 - 1
else // n is even
    rel = (n - 1) + n / 2

for i in [3, n)
    for j in [i+1, n)
        if gcd(i, j) == 1
            ++rel;
return rel / total

通过这种方法,我可以减少两个循环,但最坏的情况下时间复杂性仍然存在O(n^2).

问题:我的问题是我们是否可以利用除上述之外的任何数学属性来找到线性时间内的所需概率？

谢谢.

Answer 1

您需要计算从1到n的所有整数的Euler's Totient函数.Euler的tot或phi函数φ(n)是一个算术函数,它计算小于或等于n的正整数的数量,它们是n的相对素数.

要有效地计算函数,您可以使用Sieve of Eratosthenes的修改版本.

这是一个示例C++代码 -

#include <stdio.h>

#define MAXN 10000000

int phi[MAXN+1];
bool isPrime[MAXN+1];

void calculate_phi() {
    int i,j;
    for(i = 1; i <= MAXN; i++) {
        phi[i] = i;
        isPrime[i] = true;
    }

    for(i = 2; i <= MAXN; i++) if(isPrime[i]) {
        for(j = i+i; j <= MAXN; j+=i) {
            isPrime[j] = false;
            phi[j] = (phi[j] / i) * (i-1);
        }
    }

    for(i = 1; i <= MAXN; i++) {
        if(phi[i] == i) phi[i]--;
    }
}

int main() {
    calculate_phi();
    return 0;
}

它使用了Totient Function维基百科页面上描述的Euler产品公式.

计算这个算法的复杂性有点棘手,但它远不如此O(n^2).你可以n = 10^7很快得到结果.