Project Euler Problem 387 - Harshad Numbers - 深度优先
Project Euler Problem 387 - Harshad Numbers - 深度优先
BlackJoker 发表于2年前
Project Euler Problem 387 - Harshad Numbers - 深度优先
• 发表于 2年前
• 阅读 17
• 收藏 0
• 评论 0

原题

A Harshad or Niven number is a number that is divisible by the sum of its digits. 201 is a Harshad number because it is divisible by 3 (the sum of its digits.) When we truncate the last digit from 201, we get 20, which is a Harshad number. When we truncate the last digit from 20, we get 2, which is also a Harshad number. Let's call a Harshad number that, while recursively truncating the last digit, always results in a Harshad number a right truncatable Harshad number.

Also: 201/3=67 which is prime. Let's call a Harshad number that, when divided by the sum of its digits, results in a prime a strong Harshad number.

Now take the number 2011 which is prime. When we truncate the last digit from it we get 201, a strong Harshad number that is also right truncatable. Let's call such primes strong, right truncatable Harshad primes.

You are given that the sum of the strong, right truncatable Harshad primes less than 10000 is 90619.

Find the sum of the strong, right truncatable Harshad primes less than 10<sup>14<sup>.

分析

• right truncatable Harshad number :循环截掉哈沙德数右边一个数字，新数字还是哈沙德数

• 思路一：基于素数搜索。 从11开始遍历下一个素数，判断它是不是满足条件的素数，把满足条件的素数相加直到10<sup>14</sup>;
• 思路二：基数哈沙德数搜索。 从数字1 ~ 9开始(1 ~ 9都是哈沙德数)，深度遍历搜索哈沙德数，在哈沙德数基础上递归搜索这个数末尾加上0~9之后是否素数，是否是哈沙德数，以此遍历下去。每次在末尾添加0 ~ 9 可以保证哈沙德数都是right truncatable的，无需而外运算。

解题

基数哈沙德数深度优先搜索

``````static long N = (long) Math.pow(10, 14);
/**
* @param n a Right Truncatable HarshadNumber
* @param ds sum of digits of n
* @param strong n is strong HarshadNumber
*/
public static long sumHarshadNumber(long n, int ds, boolean strong) {
n = n * 10;
if (n >= N) {
return 0;
}
long sum = 0;
for (int i = 0; i <= 9; i++) {
n += i; // new n
ds += i;// new ds
if (strong && Util.isProbablePrime(n, 100)) {// new n is prime
sum += n;
}
if (n % ds == 0) { // new n is a Right Truncatable HarshadNumber,recursive
sum += sumHarshadNumber(n, ds, Util.isProbablePrime(n / ds, 100));
}
n -= i;// restore n
ds -= i;// restore ds
}
return sum;
}
``````

``````    /**
* 判断v是否可能是素数，是素数的概率为：1-1/2^certainty
* @return
*/
public static boolean isProbablePrime(long v, int certainty) {
return BigInteger.valueOf(v).isProbablePrime(certainty);
}
``````

求和

``````    public static void main(String[] args) {
long s = System.nanoTime();
System.out.println("Time consumed : " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - s) + " ms");
}
long sum = 0;
for (int i = 1; i < 9; i++) {
}
return sum;
}
``````

输出

``````696067597313468
Time consumed : 168 ms
``````

×