c - 乘积小于给定数字的数字对数

试图找到一种更有效的算法来寻找乘积小于给定输入的数对。
尝试使用以下内容：

                k = N - 1;
        while(k>0)
        {
            div = N/k;
            if(N%k==0)
                div--;
            ans+=div;
            k--;
        }

它做这项工作的速度相当慢有没有更有效的方法？

最佳答案

注意，如果两个数的乘积小于n，则其中至少一个数小于n的平方根（矛盾证明：否则，两个数的乘积不小于sqrt(n)）。
因此，您可以查看所有整数n到a而不是所有整数sqrt(n - 1)。
对于每个n，计算a的数目，使b >= a。
然后将结果乘以2，计算每对a * b < n的(b, a)。
之后，减去(a, b)的整数部分，以确保sqrt(n - 1)对被精确计数一次。
例如，当(a, a)时，八个可能的对是n = 5，(1, 1)，(1, 2)，(1, 3)，(1, 4)，(2, 1)，(2, 2)，(3, 1)和(4, 1)对于a = 1，我们有1 <= b <= 4，所以我们在答案中加上4对于a = 2，我们有2 <= b <= 2，所以在答案中加1我们得到总数5乘以2再减去2得到8。

关于c - 乘积小于给定数字的数字对数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/22881541/