一点一点前进...

0%

欧拉项目 | 题目357 | 质数相关问题

发表于 分类于 ， Disqus：

题目大致是说，
30能够分解得到的因数分别是1,2,3,5,6,10,15,30
对于30的每一个因数d，d+30/d都是一个质数。

求不超过100000000，且满足性质：
n的每一个因数d，d+n/d都是质数
的n的和。

分析一下什么样的n满足上述性质。
n能够分解成一系列的因数，记做d1, d2, d3, … c3, c2, c1
其中c1 * d1 = n => d1 = n / c1
也就是说只要分析前面一半，小于sqrt(n)的因数即可。

第一个因数肯定是1，那么1 + n 是质数。
所以我先使用筛选法得到小于100000000的质数，然后都减去1，得到的数才可能满足题意。

1
2
3
4
5
6
7
long[] primes = Utils.GenPrimes(100000000);

List<int> alternativeNumbers = new List<int>();
for (int i = 0; i < primes.Length; i++)
{
	alternativeNumbers.Add((int)primes[i] - 1);
}

假如n能整除4，也就是说n = 4k，第二个因数是2，且n / 2 = 2k
2 + 2k是偶数，肯定不是质数，所以我们把能整除4的数排除。
同理，n也不能被9整除。但是剩余数能被9整除的也就只有几十万了，对于二百八十多万来说，差距不大，就没有用这条性质再过滤数据了。

1
alternativeNumbers = alternativeNumbers.Where(i => i % 4 != 0).ToList();

现在，从剩余的n中看有多少是满足题意的。
正如上面所分析的，只要分析前面一半，小于sqrt(n)的因数即可。这能节省一半的时间呢。

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
long result = 0;
foreach (int n in alternativeNumbers)
{
	bool meet = true;
	int h = (int)Math.Sqrt(n);
	for (int i = 2; i <= h; i++)
	{
		if (n % i != 0)
		{
			continue;
		}

		int d = n / i;
		if (Array.BinarySearch(primes, d + i) < 0)
		{
			meet = false;
			break;
		}
	}

	if (meet)
	{
		result += n;
	}
}

return result;

我们之前已经得到了1亿之前的所有质数，那么利用二分法来判断是否是质数比传统的方式要快很多。
整个流程大约用时25s。
可优化的地方还很多，比如在筛选法的时候，使用了长度为1亿bool数组而不是bitset；多次去整理数组，这也是没有必要的，要知道，每次创建一个数百万大小的数组并复制所有的值，还是很耗时间的。