文章目录
  1. 1. 原题
  2. 2. 分析
    1. 2.1. 穷举法
  3. 3. 利用乘法竖式
    1. 3.1. 迭代 step1
    2. 3.2. 迭代step2
    3. 3.3. 迭代 step3
    4. 3.4. 因数表
    5. 3.5. 输出
  4. 4. 利用中国剩余定理 (孙子定理)

Project Euler 134 ,求以整数p1结尾,且整除另一个整数p2的数。Completed on 2015-10-19 16:42

原题

Consider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.

In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.

Find ∑ S for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.

对于连续素数对p1,p2,存在一个整数n,满足:n以p1结尾,而且n整除p2。设S为满足条件的n中的最小值,求∑ S,使得 5 ≤ p1 ≤ 1000000

分析

根据条件“n以p1结尾”可以得出:

n = p1 + k*n0         (1

其中n0是满足n0 > p1的10的最小幂,k是整数。很自然可以想到从1循环k,根据(1)式求得n,然后检验n是否整除p2。于是得到

穷举法

/**
* get the min integer n which endWiths p1 and can be divided by p2
*/

public static long getProductEndWith(int p1, int p2) {
int size = Util.getSize(p1);
long n0 = (long) Math.pow(10, size);
long n = p1 + n0;
while (true) {
if (n % p2 == 0) {
return n;
}
n += n0;
}
}

这个方法搜索5 ~ 1000000以内的素数,花费时间大概是5分钟左右。

利用乘法竖式

回忆两个整数相乘时是如何进位和相加的,举例说明,对于p1=101,p2=103,乘法算式如下:

   1   0   3
...x3 x2 x1
______________________

....
_______________________

...1 0 1

中间用”…”省略未知的数字和运算过程。

迭代 step1

由于3*x1 的个位数是1,即3*x1 % 10 = 1,于是得到x1=7,于是103 * 7 = 721

   1   0   3
...x3 x2 7
______________________
7 2 1
....
_______________________

...1 0 1

迭代step2

由于 3 * x2 + 2 的个位数是0,从而得出x2 = 6 :

   1   0   3
...x3 6 7
______________________
7 2 1
6 1 8
....
_______________________
...1 0 1

整理得到:

   1   0   3
...x3 6 7
______________________
6 9 0 1
....
_______________________
...1 0 1

迭代 step3

由于 3 * x3 +9 的个位数是1,从而得到x3 = 4,带入上面竖式得到:

      1   0   3
...4 6 7
______________________
6 9 0 1
4 1 2
_______________________
4 8 1 0 1

经过3次迭代得到n= 48101 = 467 * 103 满足条件。

因数表

上面根据个位上的数字确定因数的方法可以做一张10x10的因数表(不是九九乘法表),代码如下:

/**
* 因子multiplier[i][j] = k,满足 j = i * k % 10
*/
public static int[][] multiplier = new int[10][10];
static {
for (int i = 0; i < 10; i++) {
for (int k = 0; k < 10; k++) {
int j = i * k % 10;
multiplier[i][j] = k;
}
}
}

核心代码:

/**
* get the minimum integer n which endWiths p1 and can be divided by p2
*
* @param p1
* @param p2
* @return
*/

public static long getProductEndWith(int p1, int p2) {
int i = getRightmostKthDigit(p2, 0);// rightmost digit of p2
long n = 0;
int L = ((int) Math.log10(p1)) + 1;// size of digits of p1
for (int k = 0; k < L; k++) {// from the rightmost xth
// (10 + p1右起第k位 - n右起第k位 )%10得到这次乘积的个位数字j
int j = (10 + getRightmostKthDigit(p1, k) - getRightmostKthDigit(n, k)) % 10;
long m = multiplier[i][j];// 乘积的各位数字是j,一个因子是i,则另一个因子是m
n += p2 * (m * (int) Math.pow(10, k));// 因子m在k位上,所以要乘10^k然后加到n
}
return n;
}

从p1=5开始累加:

public static void main(String[] args) {
long s = System.currentTimeMillis();
int L = BigInteger.valueOf(1000000).nextProbablePrime().intValue();// 1000003
int[] primes = Util.getPrimesBlow(L);// last 2 is 999983,1000003
long sum = 0;
System.out.println(getProductEndWith(999983, 1000003));
for (int i = 2; i <= primes.length - 2; i++) {
int p1 = primes[i];
int p2 = primes[i + 1];
sum += Util.getProductEndWith(p1, p2);
}
System.out.println(sum);
System.out.println("Time consumed:" + (System.currentTimeMillis() - s) + " ms");
}

输出

18613426663617118
Time consumed:100 ms

利用中国剩余定理 (孙子定理)

Thread 134 -Project Euler里面有看到使用ChineseRemainder算法,时间在20s内,但是没有看懂,以后有时间再研究。
TODO

文章目录
  1. 1. 原题
  2. 2. 分析
    1. 2.1. 穷举法
  3. 3. 利用乘法竖式
    1. 3.1. 迭代 step1
    2. 3.2. 迭代step2
    3. 3.3. 迭代 step3
    4. 3.4. 因数表
    5. 3.5. 输出
  4. 4. 利用中国剩余定理 (孙子定理)