### Prime pair connection题号：134 难度： 45 中英对照

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.

### Code

public final class p134 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public String run(){
long sum = 0;
int[] primes = listPrimes(2000000);
for (int i = 3; primes[i] <= 1000000; i++) {
int p = primes[i];
int q = primes[i + 1];
int k = 1;
while (k < p)
k *= 10;
int k_1=reciprocalMod(k % q, q);
int _p=q-p;
long m = (long)_p * k_1 % q;
sum += m * k + p;
}
return Long.toString(sum);
}

// Returns x^-1 mod m, where the result is in the range [0, m). Note that (x * x^-1) mod m = (x^-1 * x) mod m = 1.
public static int reciprocalMod(int x, int m) {
if (!(m > 0 && 0 <= x && x < m))
throw new IllegalArgumentException();
// Based on a simplification of the extended Euclidean algorithm
int y = x;
x = m;
int a = 0;
int b = 1;
while (y != 0) {
int z = x % y;
int c = a - x / y * b;
x = y;
y = z;
a = b;
b = c;
}
if (x == 1)
return (a + m) % m;
else
throw new IllegalArgumentException("Reciprocal does not exist");
}

static public int[] listPrimes(int N){
int[] prime=new int[N+1];
for(int i=0;i<prime.length;i++) prime[i]=0;
for(int i=2;i<=N;i++){
if(prime[i]==0) prime[++prime[0]]=i;
for(int j=1;j<=prime[0] && prime[j]<=N/i;j++){
prime[prime[j]*i]=1;
if(i%prime[j]==0) break;
}
}
return prime;
}

}
18613426663617118
47ms