一点一点前进...

0%

欧拉项目 | 187题 | 两个素数乘积

发表于 分类于 ， Disqus：

187题链接

一个合数可以分解成至少两个质数的乘积，很多合数只能分解成两个质数的乘积，比如9 = 3 * 3，10 = 2 * 5，小于10^8次方的数字中，有多少个能分解成两个质数相乘？9和10就是满足题意的，而12 = 2 * 2 * 3就是不满足题意的。

分解质因数是比较复杂的，但是给两个质数，得到乘积，看是否小于MAX还是很简单的。
进一步，我们没必要用两层for循环得到所有满足题意的数，只要知道有几个就可以了。
比如我们有一个质数p，得到比MAX/p小的质数的个数就可以了。
先生成一个系列的质数，二分查找得到MAX/p所在的位置即可。
下面是代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static long GetAnswer()
{
    var primes = Utils.GenPrimes(MAX / 2);
    long count = 0;
    foreach (var p in primes)
    {
        long m = MAX / p;
        int index = Array.BinarySearch(primes, m);
        if (index >= 0)
        {
            count += index + 1;
        }
        else
        {
            count += ~index;
        }
    }

    count += ~Array.BinarySearch(primes, (long)Math.Sqrt(MAX));

    return count / 2;
}

对于非完全平方数，我们在foreach里面计算了2次，对于完全平方数，我们只计算了一次，于是乎，再加一次完全平方数的个数，最后统一的除以2。