当前位置:首页 » Project Euler » 详细页

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.

Solution

设两个连续素数是$p,q\quad (p< q)$,并且设$k$是最小的满足$10^k>p$。 那么题目所寻找的数即为$n=mk+p$,满需$q|n$,且需要最小化$m$。 考察$mk+p \equiv 0\quad (mod q)$,有: $$mk\equiv q-p\quad (mod q)$$ 设$k^{-1}$满足$k^{-1}\times k \equiv 0 \quad (mod q)$,称为$k$在模$q$意义下的逆。 于是 $$m\equiv (q-p)\times k^{-1} \quad (mod q)$$ 最小的$m$显然$m< q$,即为$m_{min}=\left[ (q-p)\times k^{-1} \right] \quad mod \quad q$。

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