primes - Product of three primes divisible by sum of those primes

Question

I found this problem in a cp contest which is over now so it can be answered. Three primes (p1,p2,p3) (not necessarily distinct) are called special if (p1+p2+p3) divides p1*p2*p3. We have to find the number of these special pairs if the primes can't exceed 10^6

I tried brute force method but it timed out. Can there be any other method?

标签： primessieve-of-eratosthenes

Answer 1

如果您超时，那么您需要进行一些智能搜索以替换蛮力。一百万以下的质数只有不到 80,000 个，所以你超时也就不足为奇了。

所以，你需要开始更仔细地寻找。

例如，p+2 也是素数的任何三元组 (2, p, p+2) 都将满足标准：

• 2 + 3 + 5 = 10；2 * 3 * 5 = 30；30 / 10 = 3。
• 2 + 5 + 7 = 14；2 * 5 * 7 = 70。70 / 14 = 5。
• ...
• 2 + p + p+2 = 2(p+2); 2 * p * (p+2) = 2p(p+2); 2p(p+2) / 2(p+2) = p。
• ...

还有其他以 2 开头的三元组吗？有以 3 开头的三元组吗？如果 p1=3，p2 和 p3 取什么形式？运行你的程序，最多 500 个左右，并在结果中寻找模式。然后将这些结果外推到 10^6。

我假设您正在使用 Sieve 生成​​初始素数列表。