学步园

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

分析：1位数数字易得，2位数以上，实际上是1，3，7，9的组合，这里程序用到了组合，代码有点长，但是快。

public class P35 {<br /> static int[] onlyNums = { 1, 3, 7, 9 };<br /> static int max = 1000000;<br /> static boolean[] sieve = new boolean[max];<br /> // 递归1，3，7，9的组合<br /> // length : 数字的长度<br /> private static void combination(int before, int length) {<br /> if (length == 1) {<br /> for (int i : onlyNums) {<br /> if (!sieve[i]) {<br /> rotation(before * 10 + i);<br /> }<br /> }<br /> return;<br /> }<br /> for (int i : onlyNums) {<br /> combination(before * 10 + i, length - 1);<br /> }<br /> }<br /> // 旋转，判断是否全是素数。<br /> private static void rotation(int num) {<br /> int basic = 0;<br /> int step = 0;<br /> if (num < 100) {<br /> basic = 10;<br /> step = 2;<br /> } else if (num < 1000) {<br /> basic = 100;<br /> step = 3;<br /> } else if (num < 10000) {<br /> basic = 1000;<br /> step = 4;<br /> } else if (num < 100000) {<br /> basic = 10000;<br /> step = 5;<br /> } else if (num < 1000000) {<br /> basic = 100000;<br /> step = 6;<br /> }<br /> int[] store = new int[step];<br /> for (int i = 0; i < step; i++) {<br /> if (i == 0) {<br /> store[i] = num;<br /> } else {<br /> store[i] = store[i - 1] % 10 * basic<br /> + store[i - 1] / 10;<br /> }<br /> if (!isPrime(store[i])) {<br /> return;<br /> }<br /> }<br /> for (int i : store) {<br /> System.out.println(i);<br /> sieve[i] = true;<br /> }<br /> }<br /> // 判断是否为素数<br /> private static boolean isPrime(int i) {<br /> for (int j = 2; j <= Math.sqrt(i); j++) {<br /> if (i % j == 0) {<br /> return false;<br /> }<br /> }<br /> return true;<br /> }<br /> public static void main(String[] args) {<br /> T.b();// 开始计算时间<br /> // 从2位数到6位数<br /> for (int i = 2; i <= 6; i++) {<br /> combination(0, i);<br /> }<br /> int count = 4;<br /> for (boolean b0 : sieve) {<br /> if (b0)<br /> count++;<br /> }<br /> System.out.println(count);<br /> T.e();// 打印时间<br /> }<br /> }<br />

Problem 36

The decimal number, 585 = 1001001001₂
(binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

 

分析：求的是1000000以下的数字，在二进制及十进制情况下均是回文数，偶数当然不行（2进制下最后是0，所以T掉）

public class P36 {<br /> //是否回文数<br /> private static boolean isPalindromic(Object o) {<br /> char[] cs = o.toString().toCharArray();<br /> for (int i = 0; i < cs.length / 2; i++) {<br /> if (cs[i] != cs[cs.length - 1 - i]) {<br /> return false;<br /> }<br /> }<br /> return true;<br /> }<br /> public static void main(String[] args) {<br /> int max = 1000000;<br /> int sum = 0;<br /> for (int i = 1; i < max; i+=2) {<br /> if (isPalindromic(i)<br /> && isPalindromic(Integer<br /> .toBinaryString(i))) {<br /> System.out.printf("%d : %s/n",i,Integer.toBinaryString(i));<br /> sum+=i;<br /> }<br /> }<br /> System.out.println(sum);<br /> }<br /> }

 

Problem 37

14 February 2003

The number 3797 has an interesting property. Being prime itself, it
is possible to continuously remove digits from left to right, and
remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work
from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

 

分析：判断这个数是否素数（并置于一个数组中），然后再从左到右或从右到左，判断素数数组是否含有该数

public class P37 {<br /> static List<Integer> primes = new ArrayList<Integer>();<br /> static int[] result = new int[11];<br /> public static void main(String[] args) {<br /> find();<br /> }<br /> public static void find() {<br /> primes.add(2);<br /> int sum = 0;<br /> int count = 0;<br /> for (int i = 3;; i += 2) {<br /> boolean isPrime = true;<br /> int sqrt = (int) Math.sqrt(i);<br /> for (int p : primes) {<br /> if (p > sqrt)<br /> break;<br /> if (i % p == 0) {<br /> isPrime = false;<br /> break;<br /> }<br /> }<br /> if (isPrime) {<br /> primes.add(i);<br /> if (i > 10 && isTruncatable(i)) {<br /> sum += i;<br /> count++;<br /> System.out.println(i);<br /> if (count >= 11) {// 据题意，只有11个这样的数字<br /> break;<br /> }<br /> }<br /> }<br /> }<br /> System.out.println(sum);<br /> }<br /> // 是否从左到右及从右到左均是素数<br /> public static boolean isTruncatable(int num) {<br /> int step = 10;<br /> while (num > step) {<br /> int temp0 = num % step;// 从左到右<br /> int temp1 = num / step;// 从右到左<br /> // 在素数列表中是否存在<br /> if (Collections.binarySearch(primes, temp0) < 0<br /> || Collections.binarySearch(primes,<br /> temp1) < 0) {<br /> return false;<br /> }<br /> step *= 10;<br /> }<br /> return true;<br /> }<br /> }<br />

 

Problem 38

28 February 2003

Take the number 192 and multiply it by each of 1, 2, and 3:

192
1 = 192
192
2 = 384
192
3 = 576

By concatenating each product we get the 1 to 9 pandigital,
192384576. We will call 192384576 the concatenated product of 192 and
(1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2,
3, 4, and 5, giving the pandigital, 918273645, which is the
concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be
formed as the concatenated product of an integer with (1,2, ... , n
) where n

1?

 

分析：用笔算出每种位数的上下限即可

 

public class P38 {<br /> private static int[] result = new int[5];<br /> private static int c = 0;<br /> public static boolean pandigital(int num) {<br /> if (num < 10) {<br /> c = 1;<br /> if (num < 5) {<br /> return false;<br /> }<br /> } else if (num < 100) {<br /> c = 2;<br /> if (num > 33 || num < 25) {<br /> return false;<br /> }<br /> } else if (num < 1000) {<br /> c = 3;<br /> if (num > 333) {<br /> return false;<br /> }<br /> } else if (num < 10000) {<br /> c = 4;<br /> if (num < 5000) {<br /> return false;<br /> }<br /> } else {<br /> return false;<br /> }<br /> for (int i = 0; i < c; i++) {<br /> result[i] = num * (i + 1);<br /> }<br /> return is();<br /> }<br /> static String max = "";<br /> private static boolean is() {<br /> String s = "";<br /> for (int i = 0; i < 6 - c; i++) {<br /> s += result[i];<br /> }<br /> if (s.length() != 9) {<br /> return false;<br /> }<br /> for (int i = 1; i <= 9; i++) {<br /> if (s.indexOf(i + '0') < 0) {<br /> return false;<br /> }<br /> }<br /> System.out.println(s);<br /> if (s.compareTo(max) > 0) {<br /> max = s;<br /> }<br /> return true;<br /> }<br /> public static void main(String[] args) {<br /> for (int i = 0; i < 10000; i++) {<br /> if (pandigital(i)) {<br /> System.out.print("" + i + "/n");<br /> }<br /> }<br /> System.out.println(max);<br /> }<br /> }<br />

 

Problem 39

14 March 2003

If p
is the perimeter of a right angle triangle with integral length sides, {a
,b
,c
}, there are exactly three solutions for p
= 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p

1000, is the number of solutions maximised?

 

分析：没太多，勾股定理暴力

public class P39 {<br /> public static int findRightAngle(int num) {<br /> int count = 0;<br /> for (int a = 1; a < num / 3; a++) {<br /> for (int b = a; b <= (num - a) / 2; b++) {<br /> int c = num - a - b;<br /> if (isRightAngle(a, b, c)) {<br /> count++;<br /> }<br /> }<br /> }<br /> return count;<br /> }<br /> private static boolean isRightAngle(int a, int b, int c) {<br /> return (a + b > c) && a * a + b * b == c * c;<br /> }<br /> public static void main(String[] args) {<br /> int count = 0, index = 1;<br /> for (int i = 1; i < 1000; i++) {<br /> int temp = findRightAngle(i);<br /> if (temp > count) {<br /> count = temp;<br /> index = i;<br /> }<br /> }<br /> System.out.println(count + "/t" + index);<br /> }<br /> }

 

Problem 40

28 March 2003

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101
112131415161718192021...

It can be seen that the 12^th
digit of the fractional part is 1.

If d
_n

represents the n
^th
digit of the fractional part, find the value of the following expression.

d
₁d
₁₀d
₁₀₀d
₁₀₀₀d
₁₀₀₀₀d
₁₀₀₀₀₀d
_1000000

分析：此题因为有了StringBuffer这个类，我就没去思考了，所以代码读起来没技术含量。

public class P40 {<br /> public static void main(String[] args) {<br /> StringBuffer sb = new StringBuffer();<br /> for (int i = 1;; i++) {<br /> sb.append(i);<br /> if (sb.length() >= 1000000) {<br /> break;<br /> }<br /> }<br /> int b = 1;<br /> for (int i = 0; i < 7; i++) {<br /> System.out.println(b + "/t" + sb.charAt(b - 1));<br /> b *= 10;<br /> }<br /> }<br /> }<br />

这个网站后面很多用到的数学知识及算法对我来说有点困难，唉，啃这些书真累。。。