Project Euler

Euler 34

答案：40730

1 我用程序算了无数次都是145，蛋疼，最后拿别人的程序仔细对比……
2 原来 0！=1……
3 真蛋疼，我竟然连基础数学都忘了

View Code

Euler-44

根据公式容易得出：Pmin + Pj = Pk; Pj + Pk = Pmax。

遍历 Pmin 和 Pj，如果 Pmin + Pj 结果是 Pentagonal，那么 Pk = Pmin + Pj；继续算 Pk + Pj 的结果是否等于 Pentagonal 即可。

刚开始以 Pmin 为基准往后求解，算了十多分钟也没算出个结果，吃个饭静了下思路改成从 Pmax 为基准往前求解，秒出结果。

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 #define MAX_LEN 10000
 5 
 6 int isPentagonal(int num)
 7 {
 8     int n = sqrt(num * 2.0 / 3 + 1.0/3);
 9     if (3*n*n - n == num * 2)
10         return n;
11     n++;
12     if (3*n*n - n == num * 2)
13         return n;
14     return 0;
15 }
16 
17 int main()
18 {
19     __int64 n, i, j, k;
20     __int64 Pentagonal[MAX_LEN];
21 
22     for (i = 1; i < MAX_LEN; i++)
23     {
24         Pentagonal[i] = (3*i*i-i)/2;
25         for (j = i-1; j > 0; j--)
26         {
27             n = isPentagonal(Pentagonal[i] - Pentagonal[j]);
28             if (n)
29             {
30                 n = isPentagonal(Pentagonal[j] - Pentagonal[n]);
31                 if (n)
32                 {
33                     printf("result=%d
", Pentagonal[n]);
34                     break;
35                 }
36             }
37         }
38         if (j) break;
39     }
40     return 0;
41 }

Euler-44

Euler-45

刚开始，直接算，算了一分钟还没出结果。。。

优化了下，秒出结果

 1 int main()
 2 {
 3    DWORD next_tri = 40755;
 4    DWORD ind_tri = 285;
 5    DWORD next_pen = 40755;
 6    DWORD ind_pen = 165;
 7    DWORD next_hex = 40755;
 8    DWORD ind_hex = 143;
 9    while(1)
10      {
11           next_tri += ++ind_tri;
12           if (next_tri > next_pen) next_pen += (ind_pen++*3)+1;
13           if (next_tri > next_hex) next_hex += (ind_hex++ *4)+1;
14 
15           if(next_tri == next_pen && next_tri == next_hex)
16           {
17               cout<<"solution: "<<next_tri<<endl;
18               return 0;
19           }
20     }

Euler-45

Euler-46

odd composite 其实是奇数&合数的意思

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 #define MAX_LEN 10000
 5 
 6 int prime[MAX_LEN]; //0-素数， 1-非素数
 7 int goldbach[MAX_LEN];
 8 
 9 int main()
10 {
11     int i, j, num;
12     for (i = 2; i < MAX_LEN; i++)
13     {
14         if (prime[i] == 0)
15         {
16             for (j = i + i; j< MAX_LEN; j+= i)
17             {
18                 prime[j] = 1;
19             }
20         }
21     }
22     goldbach[1] = 1;
23     for (i = 1; i < MAX_LEN; i+= 2)
24     {
25         if (goldbach[i] == 0 && prime[i] == 1) //不满足i + j*j*2，且为合数
26         {
27             printf("result=%d
", i);
28         }
29         if (prime[i] == 0)
30         {
31             for (j = 1; j < sqrt(MAX_LEN); j ++)
32             {
33                 num = i + j*j*2;
34                 if (num < MAX_LEN)
35                 {
36                     goldbach[num] = 1;
37                 }
38             }
39         }
40     }
41     return 0;
42 }

View Code

Euler-47

其实就是求每个数有多少个素数公约数

 1 #include <stdio.h>
 2 #include <math.h>
 3 
 4 #define MAX_LEN 1000000
 5 #define DISTINCT_COUNT 4
 6 
 7 int isPrime[MAX_LEN]; //0-素数， 1-非素数
 8 int num[MAX_LEN];
 9 
10 int main()
11 {
12     int i, j, k, count;
13     for (i = 2; i < MAX_LEN; i++)
14     {
15         if (isPrime[i] == 0)
16         {
17             for (j = i + i; j < MAX_LEN; j+= i)
18             {
19                 isPrime[j] = 1;
20             }
21             for (k = i; k < MAX_LEN; k+= i)
22             {
23                 num[k] ++;
24             }
25         }
26     }
27 
28     count = 0;
29     for (i = 2; i < MAX_LEN; i ++)
30     {
31         if (num[i] == DISTINCT_COUNT)
32         {
33             count ++;
34             if (count == DISTINCT_COUNT)
35             {
36                 printf("result=%d", i - DISTINCT_COUNT + 1);
37                 break;
38             }
39         }
40         else
41         {
42             count = 0;
43         }
44     }
45 
46     return 0;
47 }

View Code

Euler-50

1 什么好说的，就是考阅读理解了。
2 求素数之和，要求连续的素数个数要是最多的，而且连续素数之和也是素数。

View Code

Euler-51

暴力解法，400秒，囧。

其实求出两个素数的相同处以后，把不同的位置上分别用0~9去算一遍应该更快，刚想到就出结果了，那也懒的再改了哈哈。

  1 #include <stdio.h>
  2 #include <math.h>
  3 
  4 #define MAX_LEN 1000000
  5 #define REPLACEMENTS_LEN 8
  6 
  7 int isPrime[MAX_LEN]; //0-素数， 1-非素数
  8 
  9 /**获取相同部分，相同部分用数字字符表示，不同部分用'.'表示， 注意结果是倒的*/
 10 char *getdiff(int i, int j)
 11 {
 12     static char diff[10] = "";
 13     int count = 0;
 14     char diffchar = '';
 15     char diffchar2 = '';
 16     memset(diff, 0, sizeof(diff));
 17     while (i > 0)
 18     {
 19         if (i%10 == j%10)
 20         {
 21             diff[count] = i%10 + '0';
 22         }
 23         else
 24         {
 25             if (diffchar == '')
 26             {
 27                 diffchar = i % 10 + '0';
 28             }
 29             if (diffchar < REPLACEMENTS_LEN-1+'0' || diffchar != i % 10 + '0')
 30             {
 31                 return "";
 32             }
 33             if (diffchar2 == '')
 34             {
 35                 diffchar2 = j % 10 + '0';
 36             }
 37             if (diffchar2 < REPLACEMENTS_LEN-2+'0' || diffchar2 != j % 10 + '0')
 38             {
 39                 return "";
 40             }
 41             diff[count] = '.';
 42         }
 43         i /= 10;
 44         j /= 10;
 45         count ++;
 46     }
 47     return diff;
 48 }
 49 
 50 int check(int num, char *diff, int nth)
 51 {
 52     int idifflen = strlen(diff);
 53     int count = 0;
 54     char diffchar = '.';
 55     while (num > 0)
 56     {
 57         if (diff[count] == '')
 58         {
 59             return 0;
 60         }
 61         if (diff[count] != '.' && diff[count] != num % 10 + '0')
 62         {
 63             return 0;
 64         }
 65         if (diff[count] == '.')
 66         {
 67             if (diffchar == '.')
 68                 diffchar = num % 10 + '0';
 69             if (diffchar != num % 10 + '0' || diffchar < REPLACEMENTS_LEN-nth+'0')
 70                 return 0;
 71         }
 72         count ++;
 73         num /= 10;
 74     }
 75     if (diff[count] == '')
 76     {
 77         return 1;
 78     }
 79     return 0;
 80 }
 81 
 82 int main()
 83 {
 84     int i, j, k, count, len, maxlen = 6;
 85     char diff[10];
 86     for (i = 2; i < MAX_LEN; i++)
 87     {
 88         if (isPrime[i] == 0)
 89         {
 90             for (j = i + i; j < MAX_LEN; j+= i)
 91             {
 92                 isPrime[j] = 1;
 93             }
 94         }
 95     }
 96 
 97 /**
 98  *1.找两个素数之间相同的部分
 99  *2.往前找所有素数，如果有相同的部分，记录count
100  *  注意，如果是两位相同，这两位的数字必然是相同的数字
101  */
102     for (i = 10; i < MAX_LEN; i++)
103     {
104         if (isPrime[i] == 0)
105         {
106             for (j = i - 1; j > 10; j -- )
107             {
108                 count = 1;
109                 if (isPrime[j] == 0)
110                 {
111                     strcpy(diff, getdiff(i, j));
112                     if (diff[0] != '')
113                     {
114                         count = 2;
115                         for (k = j-1; k > 10; k --)
116                         {
117                             if (isPrime[k] == 0)
118                             {
119                                 count += check(k, diff, count+1);
120                                 if (count == REPLACEMENTS_LEN) //先用3试试水
121                                 {
122                                     printf("%d,", k);
123                                     break;
124                                 }
125                             }
126                         }
127                     }
128                     if (count == REPLACEMENTS_LEN)
129                     {
130                         printf("%d,", j);
131                         break;
132                     }
133                 }
134             }
135         }
136         if (count == REPLACEMENTS_LEN)
137         {
138             printf("%d
", i);
139             break;
140         }
141     }
142 
143     //printf("%d", check(56663, "3..65"));
144 
145     return 0;
146 }

View Code