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

Prime pair sets 题号:60 难度: 20 中英对照

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

Solution

本题可采用暴力搜寻方法寻找出符合条件的质数的和,并使用一些技巧降低时间复杂度。我们先预估计一个初始值$SumLimit$,它表示找到符合条件的质数集合的和的上限。如代码中取值$100000$。 1. 使用[Prime Sieve](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)方法得到小于$SumLimit$的质数构成的集合$primeSet$。 2. 在$PrimeSet$集合中,寻找一个$size$为$5$的质数集合,它满足任取两数字按任意顺序连接起来仍为质数的集合(以下简称为条件$T$),并且这个质数集合的和$sum$不能超过$SumLimit$ 3. 如果找到了这样的集合,则将$SumLimit$的值更新为$sum$,且$primeSet$的更新为所有小于$sum$的质数集合,返回步骤2 。如果找不到这样的集合,则返回  当前的$SumLimit$。 (如果,第一个次寻找就找不到符合条件的质数集合,则适当调大$SumLimit$的初始值) 一次寻找符合条件的质数集合过程如下,以满足$size=5$ $SumLimit=100000$为例: 1. 初始化$i=0$$,prefix$={$primeSet$[$i$]} (即将第一个质数2放入$prefix$集合)。$prefix$表示目前符合条件的质数的集合。 2. 从$primeSet[i]$的下一个质数开始,遍历 $primeSet$,找到与当前集合$prefix$ 的任意质数满足条件$T$的质数$primeSet[j]$,将$primeSet[j]$加入到$prefix$中。 3. 若找到了$5$个满足互换条件$T$的元素且它们和不大于$100000$,则返回它们的和。否则$i=i+1$,若此时$i$大于了$primeSet$ 的$size$,则返回-1(即,找不到符合条件的质数集合),否则,$prefix$ 重置为{$primeSet$[$i$]},回到步骤2 该方法主要降低时间的方法主要有两点: 1. 设置$SumLimit$以减少需要遍历的质数的范围 2. 使用表(数组)保存已经判断过的元素是否为质数的信息(避免了重复判断)。

Code

import java.util.Arrays;
import java.util.BitSet;


public final class p60{
	
	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");	
	}
	
	
	private static final int PRIME_LIMIT = 100000;  // 预估计的质数的大小
	
	private static int[] primes = listPrimes(PRIME_LIMIT); //小于PRIME_LIMIT的所有质数
	
	private static BitSet isConcatPrimeKnown; //保存一个数字是否已经判断过它是否为质数
	private static BitSet isConcatPrime; //保存一个数字是否为质数
	
	
	public static long run() {
		isConcatPrimeKnown = new BitSet(primes.length * primes.length);
		isConcatPrime      = new BitSet(primes.length * primes.length);
		
		int sumLimit = PRIME_LIMIT;
		while (true) {
			int sum = findSetSum(new int[]{}, 5, sumLimit - 1);
			if (sum == -1)  // 找不出再符合条件的质数集合时
				return sumLimit;
			sumLimit = sum;
		}
	}
	
	/*找到任何符合条件的质数集合,返回它们的和,如果没有找到则返回-1
	 *参数:prefix 已找到的符合条件(任取两数字按任意顺序连接起来仍为素数的集合)的质数集合
	 *     tartgetSize 需要找到符合条件的质数集合的大小
	 *     sumLimit 对符合条件的质数的和的大小做出限制
	 *例如:findSetSum(new int[]{1,3,28},5 ,10000),意味着找到任意一个符合条件的质数集合的和。
	 *     1,3,28表示第1个质数3、第3个质数7,第28个质数109。这个集合的大小要求为5,并且这个集合中最小的三个元素为{3,7,109}
	 *     这5个元素的和不得超过100000。
	 * */
	private static int findSetSum(int[] prefix, int targetSize, int sumLimit) {
		if (prefix.length == targetSize) {
			int sum = 0;
			for (int i : prefix)
				sum += primes[i];
			return sum;
			
		} else {
			int i;
			if (prefix.length == 0)
				i = 0;
			else
				i = prefix[prefix.length - 1] + 1;
			
			outer:
			for (; i < primes.length && primes[i] <= sumLimit; i++) {
				for (int j : prefix) {
					if (!isConcatPrime(i, j) || !isConcatPrime(j, i))
						continue outer;
				}
				
				int[] appended = Arrays.copyOf(prefix, prefix.length + 1);
				appended[appended.length - 1] = i;
				int sum = findSetSum(appended, targetSize, sumLimit - primes[i]);
				if (sum != -1)
					return sum;
			}
			return -1;
		}
	}
	
	
	//判断两个数拼接起来是不是质数
	private static boolean isConcatPrime(int x, int y) {
		int index = x * primes.length + y;
		if (isConcatPrimeKnown.get(index))
			return isConcatPrime.get(index);
		
		x = primes[x];
		y = primes[y];
		int mult = 1;
		for (int temp = y; temp != 0; temp /= 10)
			mult *= 10;
		
		boolean result = isPrime((long)x * mult + y);
		isConcatPrimeKnown.set(index);
		isConcatPrime.set(index, result);
		return result;
	}
	
	//判断一个数是不是质数
	private static boolean isPrime(long x) {
		if (x < 0)
			throw new IllegalArgumentException();
		else if (x == 0 || x == 1)
			return false;
		else {
			long end = (long) Math.sqrt(x);
			for (int p : primes) {
				if (p > end)
					break;
				if (x % p == 0)
					return false;
			}
			for (long i = primes[primes.length - 1] + 2; i <= end; i += 2) {
				if (x % i == 0)
					return false;
			}
			return true;
		}
	}
	
	//获得所有质数小于n的质数
	public static int[] listPrimes(int n) {
		boolean[] isprime = listPrimality(n);
		int count = 0;
		for (boolean b : isprime) {
			if (b)
				count++;
		}
		
		int[] result = new int[count];
		for (int i = 0, j = 0; i < isprime.length; i++) {
			if (isprime[i]) {
				result[j] = i;
				j++;
			}
		}
		return result;
	}
	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;
	}

}
26033
6829ms