文档章节

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

BlackJoker
 BlackJoker
发布于 2015/10/14 11:15
字数 768
阅读 38
收藏 0

精选30+云产品,助力企业轻松上云!>>>

原题

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
深圳
高级程序员
私信 提问
加载中
请先登录后再评论。
Project Euler 516 5-smooth totients (数论)

##题目链接: https://projecteuler.net/problem=516 ##题目: $5$-smooth numbers are numbers whose largest prime factor doesn't exceed $5$. $5$-smooth numbers are also called Hammi......

osc_tbnby811
2018/01/18
5
0
Project Euler Problem 48 - 求大数的模

原题:Project Euler 48 ,获取大数 1^1 + 2^2 + ... + 1000^1000 的最后10个数字 暴力法 用[BigInteger]把这些数进行累加,并不会特别大(内存可hold住),见Java代码: 使用幂模运算规则 有...

BlackJoker
2015/10/14
30
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
69
0
Project Euler 501 Eight Divisors (数论)

##题目链接: https://projecteuler.net/problem=501 ##题意: $f(n)$ be the count of numbers not exceeding $n$ with exactly eight divisors. ###就是找少于等于 $n$中只有8个因子的个数......

osc_jjc36t9p
2018/02/18
4
0
Discrete Roots SPOJ - DISCRT(原根+指标+bsgs+exgcd)

1 #include <stdio.h> 2 #include <string.h> 3 #include"vector" 4 #include"iostream" 5 #include <algorithm> 6 #include"bits/stdc++.h" 7 using namespace std; 8 #include"map" 9 #def......

osc_nubdt7rk
2019/05/28
4
0

没有更多内容

加载失败,请刷新页面

加载更多

绕过移动端系统限制的 dlopen 库 byOpen

byOpen是一个绕过移动端系统限制的增强版dlfunctions库。 支持特性 Android 支持App中加载和使用Android系统库接口(即使maps中还没有被加载也支持)。 Android 7以上dlopen, System.load都是...

shzwork
4分钟前
0
0
Golang学习系列第二天:变量、常量、数据类型和流程语句

继golang第一天后,今天学习下golang的变量、常量、数据类型和控制流语句。 做过其他编程语言(比如JavaScript,java,python)项目的话,其实很好理解变量、常量、数据类型和控制流。 变量也...

董广明
16分钟前
13
0
redis系列之——一致性hash算法

一致性hash算法你了解吗?什么时候使用?解决什么问题?redis集群模式使用了一致性hash算法了吗? 数据分片(sharding) 分布式数据存储时,经常要考虑数据分片,避免将大量的数据放在单表或...

诸葛小猿
34分钟前
15
0
IMDB是否提供API? [关闭] - Does IMDB provide an API? [closed]

问题: I recently found a movie organizer application which fetches its data from the IMDB database . 最近,我发现了一个电影管理器应用程序,该应用程序从IMDB数据库中获取其数据。 ...

fyin1314
57分钟前
14
0
Elasticsearch系列之Query DSL

1 前言 我们先通过阅读官方文档,了解一下什么是 Query DSL 。 1.1 Query DSL Elasticsearch provides a full Query DSL (Domain Specific Language) based on JSON to define queries. DSL是......

冯文议
58分钟前
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部