数字乘积

mathe

主要是运行速度还是太慢了，毕竟在规模大起来的时候速度最重要

无心人

1. 
   
2. // prod.cpp : Defines the entry point for the console application.
   
3. //
   
4. 
   
5. #include "stdafx.h"
   
6. 
   
7. char l[100000000];
   
8. 
   
9. unsigned int prodd(unsigned int n)
   
10. {
    
11.         char c[17];
    
12.         unsigned int i, k = 1;
    
13.         sprintf(c, "%u", n);
    
14.     for (i = 0; c[i] != 0; i ++)
    
15.                 k *= (unsigned int)(c[i] - '0');
    
16.     return k;
    
17. }
    
18. 
    
19. void init(void)
    
20. {
    
21.         unsigned int i, k, n;
    
22.         for (i = 0; i <= 9; i ++)
    
23.                 l[i] = 0;
    
24. 
    
25.         for (i = 10; i < 100000000; i ++)
    
26.         l[i] = l[prodd(i)] + 1;
    
27.             
    
28.         
    
29. }       
    
30. 
    
31. int isprime(unsigned int n)
    
32. {
    
33.         if (n & 1 == 0)
    
34.                 return 0;
    
35.         else
    
36.                 if (n % 3 == 0)
    
37.                         return 0;
    
38.         if (n % 5 == 0) return 0;
    
39.         if (n % 7 == 0) return 0;
    
40.         if (n % 11 == 0) return 0;
    
41.         if (n % 13 == 0) return 0;
    
42.         if (n % 17 == 0) return 0;
    
43.         if (n % 19 == 0) return 0;
    
44.         if (n % 23 == 0) return 0;
    
45.         if (n % 29 == 0) return 0;
    
46.         if (n % 31 == 0) return 0;
    
47.     return 1;
    
48. }
    
49. 
    
50. int _tmain(int argc, _TCHAR* argv[])
    
51. {
    
52.         unsigned int i;
    
53.         init();
    
54.         printf("init finished.\n");
    
55.     for (i = 100000001; i <= 999999999; i ++)
    
56.         {
    
57.                 if (l[prodd(i)] == 9)
    
58.                         if (isprime(i))
    
59.                                 printf("%u  ", i);
    
60.         }
    
61.         return 0;
    
62. }
    

复制代码

谁来优化下

无心人

有几点需要明确的是
假设反推
需要的数字
1、大于2位的就应该位数里不能有0了
2、只含有因子2，3，5，7， 如果大于99，则只含有因子2，3，7
3、任何级别的数字都不能大于该数字的位数，否则肯定不行
（和题目的要求相符）
4、数字分解得到的数字（反推）也应该符合这个规则

我觉得从级别2开始比较好
即25以上的

无心人

这么考虑下来
27， 28， 36，45， 48， 54， 56， 63， 64， 72， 75， 84， 96是唯一的开始反推的数列

无心人

27 = 3 * 3 * 3
27 <- 39
27 <- 93
27 <- 333
27 <- 139
27 <- 193
27 <- 319
27 <- 913
27 <- 391
27 <- 931
不符合

无心人

同样的分析适合28

无心人

63 = 3 * 3 * 7
63 <- 79
63 <- 97
63 <- 337
63 <- 373
63 <- 733
63 <- 179
63 <- 197
63 <- 719
63 <- 917
63 <- 791
63 <- 971

均不符合

无心人

36 = 2 * 2 * 3 * 3
36 <- 49
36 <- 94
36 <- 263
36 <- 236
36 <- 229
36 <- 292
36 <- 343
36 <- 334
36 <- 326
36 <- 362
也不符合吧

无心人

谁能用程序分析下这几个数字
目前知道54是可以做逆推的

无心人

另外，怀疑逆推时
不能有1

否则和题目要求不符

谁证明？