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

Prime digit replacements 题号:51 难度: 15 中英对照

By replacing the 1st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3rd and 4th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

Solution

暴力求解法。对于一个数digits,逐步替换digits的某些位得到若干新的数。如果新的数中有8个质数,输出digits。 提示: 1. 如何实现替换digits中的某些位,得到新的数? 可以采用模板。先生成不同的模板,在与digits合成到一起。

Code

import java.util.Arrays;

public class p51 {
	public static void main(String[] args) {
		long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
	}
	//记录一个数是不是素数
	public static  boolean[] listPrimality(int n) {
		if (n < 0)
			throw new IllegalArgumentException("Negative array size");
		boolean[] result = new boolean[n + 1];
		if (n >= 2)
			result[2] = true;
		for (int i = 3; i <= n; i += 2)
			result[i] = true;
		
		for (int i = 3, end = (int)Math.sqrt(n); i <= end; i += 2) {
			if (result[i]) {
				for (int j = i * i; j <= n; j += i << 1)
					result[j] = false;
			}
		}
		return result;
	}
	
	public static int run() {
		boolean[] isPrime = listPrimality(1000000);
		for (int i = 0; i < isPrime.length; i++) {
			if (!isPrime[i])
				continue;
			
			int[] n = toDigits(i);
			//mask指替换的位,这里用十进制整数表示。在doMask中转为二进制
			for (int mask = 0; mask < (1 << n.length); mask++) {
				int[] digits = doMask(n, mask);
				int count = 0;
				for (int j = 0; j < 10; j++) {
					if (digits[0] != 0 && isPrime[toNumber(digits)])
						count++;
					digits = addMask(digits, mask);
				}
				
				if (count == 8) {
					digits = doMask(n, mask);
					for (int j = 0; j < 10; j++) {
						if (digits[0] != 0 && isPrime[toNumber(digits)])
							return toNumber(digits);
						digits = addMask(digits, mask);
					}
				}
			}
		}
		throw new RuntimeException("Not found");
	}
	
	//将数字转成整形数组,方便对每一位进行操作
	private static int[] toDigits(int n) {
		int[] buf = new int[10];
		int i = buf.length;
		do {
			i--;
			buf[i] = n % 10;
			n /= 10;
		} while (n != 0);
		return Arrays.copyOfRange(buf, i, buf.length);
	}
	
	//给数字digits加上模板,即替换其中的某些位
	private static int[] doMask(int[] digits, int mask) {
		int[] result = new int[digits.length];
		for (int i = 0; i < digits.length; i++)
			result[i] = digits[i] * (~mask >>> i & 1);
		return result;
	}
	
	
	private static int[] addMask(int[] digits, int mask) {
		int[] result = new int[digits.length];
		for (int i = 0; i < digits.length; i++)
			result[i] = digits[i] + (mask >>> i & 1);
		return result;
	}
	
	
	private static int toNumber(int[] digits) {
		int result = 0;
		for (int x : digits)
			result = result * 10 + x;
		return result;
	}
}
121313
132ms