一点一点前进...

0%

欧拉项目 | 347题 | 能被两个质数整除的最大整数

发表于 分类于 ， Disqus：

原题链接

在所有小于100的整数中，能被两个质数整除的最大整数是96，96 = 2^5 * 3。我们定义函数M(p,q,N)：对于不同的两个质数p和q，M(p,q,N)是小于等于N中能被p和q整除的最大整数，如果不存在，M(p,q,N)=0
比如
M(2,3,100)=96
M(3,5,100)=75，而不是90，因为90能被2，3，5整除。
M(2,73,100)=0，因为2*73=146，小于100的数里面没有数能同时被2和73整除。

S(N)是对所有不同的M(p,q,N)求和。
题目最后要求是求S(10 000 000)。

解题思路很清晰，只是要尽可能早的排除不可能的质数组合。
首先获取0到5 000 000之间的质数，因为大于5 000 000的质数乘以最小的质数2也会大于10 000 000，M是0，不用考虑了。
然后就是组合每一个可能的指数对p和q，获得M(p,q,10 000 000)。
两层循环遍历p和q。
不妨设p比较小，用遍历所有的质数吗？显然不用，当p大于10 000 000的平方时，p和q的乘积就会大于10 000 000，M是0。
q也不用遍历所有大于p的质数，一旦p和q的乘积大于10 000 000，就可以停止了。
有了p，q，得到对应的M，然后放到一个List里面。
循环遍历完之后就可以把List里面的值求和。

给定p和q，如何得到M呢？
我用了暴力法，就是先通过Log(p, 10 000 000)和Log(q, 10 000 000)计算出可能的最大指数，然后两层循环，遍历所有可能的情况，得到小于等于M且能被2个质数整除的最大值。

在我的机器上，大约2s多一点就能得到结果了。
最后，贴一下我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
const int MAX = 10000000;
public static long GetAnswer()
{
	var Ms = new List<long>();

	var primes = Utils.GenPrimes(MAX / 2);
	for (int i = 0; primes[i] < Math.Sqrt(MAX); i++)
	{
		for (int j = i + 1; j < primes.Length; j++)
		{
			long p = primes[i];
			long q = primes[j];
			if (p * q < MAX)
			{
				Ms.Add(GetM(p, q));
			}
			else
			{
				break;
			}
		}
	}

	return Ms.Sum();
}

private static long GetM(long p, long q)
{
	var max = 0L;
	var e1Max = (int)(Math.Log(MAX) / Math.Log(p));
	var e2Max = (int)(Math.Log(MAX) / Math.Log(q));
	for (int e1 = 0; e1 < e1Max; e1++)
	{
		for (int e2 = 0; e2 < e2Max; e2++)
		{
			var product = Math.Pow(p, e1 + 1) * Math.Pow(q, e2 + 1);
			if (product <= MAX && product > max)
			{
				max = (long)product;
			}
		}
	}

	return max;
}