ACM模拟题详解（2）——简单数论

有很多与数字相关的题目，主要考察基本的编程能力，如果数学比较好，对于解决这些问题有比较好的帮助。下面的题目是学生收集的题目，我进行了讲解。

1、Self Numbers
Description

In 1949 the Indian mathematician D.R. Kaprekar discovered a class of numbers called self-numbers. For any positive integer n, define d(n) to be n plus the sum of the digits of n. (The d stands for digitadition, a term coined by Kaprekar.) For example, d(75) = 75 + 7 + 5 = 87. Given any positive integer n as a starting point, you can construct the infinite increasing sequence of integers n, d(n), d(d(n)), d(d(d(n))), .... For example, if you start with 33, the next number is 33 + 3 + 3 = 39, the next is 39 + 3 + 9 = 51, the next is 51 + 5 + 1 = 57, and so you generate the sequence 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... The number n is called a generator of d(n). In the sequence above, 33 is a generator of 39, 39 is a generator of 51, 51 is a generator of 57, and so on. Some numbers have more than one generator: for example, 101 has two generators, 91 and 100. A number with no generators is a self-number. There are thirteen self-numbers less than 100: 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, and 97.

Input

No input for this problem.

Output

Write a program to output all positive self-numbers less than 10000 in increasing order, one per line.

Sample Input

Sample Output

135792031425364 | |       <-- a lot more numbers |9903991499259927993899499960997199829993

题目翻译：有这样的公式y=d(x1x2…xn)=x1+x2+…+xn+ x1x2…xn，例如：

d(123) = 123+1+2+3=129

d(55)=55+5+5=65

这里把x1x2…xn称为y的生成子，例如123是129的生成子，55是65的生成子。题目要求列出10000以内没有生成子的整数。

题目详解：对1到10000的生成子进行遍历，看能够生成哪些数字，然后把不能生成的输出即可，下面的代码供参考。

       public static void setNumbers(){              int[] numbers=new int[10000];              Arrays.fill(numbers, 0);              for(int i=1;i<10000;i++){                     int temp = i+i%10+(i/10)%10+(i/100)%10+i/1000;                     if(temp<10000)                            numbers[temp-1]=1;              }              for(int i=0;i<9999;i++){                     if(numbers[i]==0)                            System.out.println(i+1);              }       }2、Goldbachs Conjecture
Description

In 1742, Christian Goldbach, a German 易做图 mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:

Every even number greater than 4 can be written as the sum of two odd prime numbers.

For example:

8 = 3 + 5. Both 3 and 5 are odd prime numbers.
20 = 3 + 17 = 7 + 13.
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)

Anyway, your task is now to verify Goldbachs conjecture for all even numbers less than a million.

Input

The input will contain one or more test cases.Each test case consists of one even integer n with 6 <= n < 1000000. Input will be terminated by a value of 0 for n.

Output

For each test case, print one line of the form n = a + b, where a and b are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to n, choose the pair where the difference b - a is maximized. If there is no such pair, print a line saying "Goldbachs conjecture is wrong."

Sample Input

820420Sample Output

8 = 3 + 520 = 3 + 1742 = 5 + 37

翻译：据推测大于4的偶数都可以写成两个质数（素数）的和。让我们编写程序进行验证，如果有写出表达式，如果没有则输出“Goldbachs conjecture is wrong.”。如果能够写成的式子多于1个，则写出两个数字差比较大的那对。例如：

42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23

输出42 = 5 + 37即可。因为37-5最大。

题目详解：题目比较简单，只要测试两个数是否为质数即可。下面的代码供参考。

    /*     * 8 = 3 + 5     * 20 = 3 + 17     * 42 = 5 + 37     */    public static void test(int x){       if(6<=x && x < 1000000){           if(x%2!=0){              System.out.println("输入数据不是偶数！");           }else{              boolean b=false;              for(int i=3;i+i<x;i++){                  if(isPrime(i) && isPrime(x-i)){                     System.out.println(x+" = "+i+" + "+(x-i));                     b = true;                     break;                  }              }              if(!b)                  System.out.println("Goldbachs conjecture is wrong.");           }       }else{           System.out.println("输入数据范围不对");       }    }        /*     * 判断某个数是否为质数，如果是返回true     */    public static boolean isPrime(int x){       for(int i=2;i*i<=x;i++){           if(x%i==0)              return false;       }       return true;    }3、Sum of Consecutive Prime Numbers
Description

Some positive integers can be represented by a sum of one or more consecutive prime numbers. How many such representations does a given positive integer have? For e

补充：软件开发 , Java ,

上一个：ACM模拟题详解（3）——数论（续）
下一个：ACM模拟题讲解（1）-高精度