文章目录
  1. 1. 原题
  2. 2. 补偿法
    1. 2.1. 算法步骤
    2. 2.2. 复杂度分析
  3. 3. 遍历比值法
    1. 3.1. 算法步骤
    2. 3.2. Java代码实现

Problem 518 - Prime triples and geometric sequences ,存在一些素数三元组(a,b,c),使得(a+1,b+1,c+1)是等比数列,求108以内的所有这种三元组的元素的和。Completed on 2015-10-22 14:39

原题

Let S(n) = a+b+c over all triples (a,b,c) such that:

  • a, b, and c are prime numbers.
  • a < b < c < n.
  • a+1, b+1, and c+1 form a geometric sequence.
    For example, S(100) = 1035 with the following triples:
    (2, 5, 11), (2, 11, 47), (5, 11, 23), (5, 17, 53), (7, 11, 17), (7, 23, 71), (11, 23, 47), (17, 23, 31), (17, 41, 97), (31, 47, 71), (71, 83, 97)

Find S(108).

补偿法

根据等比数列的特征,可以得到$(a+1)(c+1)=(b+1)^2$。将$(b+1)^2$分解质因数之后,每个质因子的幂必然是偶数,从而(a+1)和(c+1)的相同的质因数的幂必然都是同奇或者同偶,那么只需要把这些奇数次质因数相乘得到一个积,那么(a+1)和(c+1)的这个积相等,把(p+1)的这个积称为质素p的补偿数 。可以利用这个结论求解这个题。

算法步骤

  1. 获取小于$N=10^8$的所有素数:primes;
  2. 遍历数组primes,给每个质素p分解质因数并把奇数次因子相乘得到complements数组,complements[i]保存素数primes[i]的补偿数;
  3. 把补偿数相同的素数放入相同的列表并排序,得到Map{complements[i] => Li},Li是补偿数为complements[i]的素数列表。
  4. 把所有素数的平方存入一个Set,遍历列表Li,如果有两个质数的积在这个Set中,则是满足条件的三元组,把它们相加;
  5. 对每个补偿数和列表进行上述操作对结果求和。

复杂度分析

用上述方法在我的T420s笔记本上跑了大概两个半小时,8核CPU呼呼转了那么久才算出来。中间有很多次因为内存溢出而失败,把内存加到4G还是溢出,后面去掉了补偿数那个Map集合以及保存相同补偿数质素列表的那些List,全部用原生的int[]进行运算才成功。

Java的包装类Integer,Long,以及对象引用本身消耗的内存在这种情况下不得不考虑。所以做大尺度的数值计算,只能用原生类型而不能用对象类型,但是Java的Set和Map等基本数据结构都是基于对象的,都是吃内存大户。这是Java在计算领域的劣势。

遍历比值法

根据等比数列得到:b+1 = (a+1)*(k/d) ,(c+1)=(b+1)*(k/d)=(a+1)* k2/d2,假设gcd(k,d)=1,则(a+1)可被d2整除。(dev_random’s answer in Thread 518)。

算法步骤

  1. 创建一个数组,flag[i]=1表示i是素数flag[i]=0表示i是合数;
  2. loop d from 1 to N with step 1,for each d ,loop n from d^2 to N with step d^2,如果flag[n-1]=1,loop k from d+1 to K with step 1。这样,已知a,k,d,可以求出另外b+1,c+1,只需判断b和c是否是质素就可以判断是否满足条件。这里K是使c+1<=N的最大数,$k^2 = {(c+1) \over (a+1)}d^2$. 得到
    $$ \frac{k^2 (a+1)}{d^2} = c+1 <= N$$

Java代码实现

public static long sumGeometricPrimeTriples(int N) {
BitSet flag = Util.getPrimeDecisionBlow2(N);
long sum = 0;
for (int d = 1; d < N; d++) {// 遍历d
long d2 = d * d;
if (d2 > N) {// when convert to int,may overflow
break;
}
for (int n = (int) d2; n < N; n += d2) {
if (flag.get(n - 1)) {// a = n-1是素数
int nd = n / d;
int ndd = n / d / d;
for (int k = d + 1; ndd * k * k <= N; k++) {// 找到a之后遍历k,根据d,k可以确定b和c
int b = nd * k - 1;
int c = ndd * k * k - 1;
if (flag.get(b) && flag.get(c) && gcd(d, k) == 1) {
// gcd这个条件去除重复统计
sum += (n - 1) + b + c;
}
}
}
}
}
return sum;
}

答案不贴出来了,在1014数量级上,运行时间,大概5秒。

文章目录
  1. 1. 原题
  2. 2. 补偿法
    1. 2.1. 算法步骤
    2. 2.2. 复杂度分析
  3. 3. 遍历比值法
    1. 3.1. 算法步骤
    2. 3.2. Java代码实现