文档章节

Project Euler Problem 387 - Harshad Numbers - 深度优先

BlackJoker
 BlackJoker
发布于 2015/10/14 11:15
字数 768
阅读 23
收藏 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>.

分析

Harshad Numbers(哈沙德数)

是可以在某个固定的进位制中,被其数位的数字之和整除的整数。

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

  • strong Harshad number:如果哈沙德数与它的各位数字之和的比值是素数。

  • strong, right truncatable Harshad primes 是这样一类素数,去掉最后一个数字后,是一个strong Harshad number也是一个right truncatable Harshad number

穷举法有两条思路:

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

实践证明,思路一不可行,10^14以内的素数不是短时间内可以遍历完的,而且对每个素数进行条件判断也比较耗时。思路二可行。

解题

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

static long N = (long) Math.pow(10, 14);
    /**
     * 按照 Truncatable HarshadNumber遍历:
     * @param n a Right Truncatable HarshadNumber
     * @param ds sum of digits of n
     * @param strong n is strong HarshadNumber
     * @return 以n为前缀的所有StrongRightTruncatableHarshad素数之和
     */
    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;
    }

其中,Util.isProbablePrime 如下:

    /**
     * 判断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(sumHarshadNumbes());
        System.out.println("Time consumed : " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - s) + " ms");
    }
    public static long sumHarshadNumbers() {
        long sum = 0;
        for (int i = 1; i < 9; i++) {
            sum += sumHarshadNumber(i, i, false);
        }
        return sum;
    }

输出

696067597313468
Time consumed : 168 ms

© 著作权归作者所有

共有 人打赏支持
BlackJoker
粉丝 1
博文 17
码字总数 9270
作品 0
深圳
高级程序员
私信 提问
Euler Project Problem 6

The sum of the squares of the first ten natural numbers is, 1 2 + 2 2 + ... + 10 2 = 385 The square of the sum of the first ten natural numbers is, (1 + 2 + ... + 10) 2 = 55 2 =......

长平狐
2012/10/16
52
0
Bad Coder(2011-01-04)

再优美的语言,如果你真的把它当作草稿来用,也还真是可以写出一些自惭形秽的-_-! 依然以奋斗在 Project Euler 界的我为例(这次的热情貌似久了一点)。 Problem 27 我们拿到的只是坐标,并非...

Pope怯懦懦地
2017/12/09
0
0
[Data Structures and Algorithms - 1] Introduction & Mathematics

References: 1. Stanford University CS97SI by Jaehyun Park 2. Introduction to Algorithms 3. Kuangbin's ACM Template 4. Data Structures by Dayou Liu 5. Euler's Totient Function Ge......

rgvb178
01/26
0
0
数值计算系统--Euler

类似Matlab、Octave、Scilab的数值计算系统。 EULER is a program for quickly and interactively computing with real and complex numbers and matrices, or with intervals, in the style......

匿名
2011/04/18
1K
0
Python中如何使用yield,对于庞大迭代的优化处理

一直困扰于yield的使用,今天看到一篇不错的解释,虽然都是英文,不过不要紧,可以跳开,直接看代码的部分就能懂 Improve Your Python: 'yield' and Generators Explained Posted on Apr 07...

青鸾之旅
2013/08/02
0
3

没有更多内容

加载失败,请刷新页面

加载更多

深入解析React中的元素、组件、实例和节点

React 深入系列,深入讲解了React中的重点概念、特性和模式等,旨在帮助大家加深对React的理解,以及在项目中更加灵活地使用React。 React 中的元素、组件、实例和节点,是React中关系密切的...

前端攻城小牛
17分钟前
2
0
菜鸟网络三面面经(java开发岗):Spring boot+JVM+线程池+中间件

一面 1、HaspMap底层原理?HaspTable和ConcurrentHashMap他们之间的相同点和不同点? 2、由上题提到锁的问题 3、MySQL的表锁&行锁&乐观锁&悲观锁,各自的使用场景 4、Java线程锁有哪些,各自的...

别打我会飞
21分钟前
2
0
NCL入门

;***这两行指令必须加载,类似于c语言中的库函数load "$NCARG_ROOT/lib/ncarg/nclscripts/csm/gsn_code.ncl"load "$NCARG_ROOT/lib/ncarg/nclscripts/csm/gsn_csm.ncl"begin ......

voole
25分钟前
1
0
程序员该如何把握黄金五年!

在Java业界流行着一种说法——黄金5年,就是从程序员入职时算起,前五年的工作选择直接影响整个职业生涯的职业发展和薪资走向。如何把握这五年,从一个刚入行的菜鸟蜕变成一个处事不惊的大佬...

James-
34分钟前
3
0
使用正则表达式实现网页爬虫的思路详解

网页爬虫:就是一个程序用于在互联网中获取指定规则的数据。这篇文章主要介绍了使用正则表达式实现网页爬虫的思路详解,需要的朋友可以参考下 网页爬虫:就是一个程序用于在互联网中获取指定规...

前端小攻略
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部