题目87：考察能写成质数的2次，3次和4次方之和的数

欧拉计划

Prime power triples

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

题目：

最小的能写成质数的 2，3，4 次方之和的数是 28。50 以下一共有 4 个数可以写成这种形式：

5000 万以下的数中有多少个能写成一个质数的 2 次方，一个质数的 3 次方和一个质数的 4 次方之和？

jerryxjr1220

1097343
[Finished in 0.7s]

1. def getPrimes(n):
   
2.         primes = [True]*n
   
3.         primes[0], primes[1] = False, False
   
4.         for (i,prime) in enumerate(primes):
   
5.                 if prime:
   
6.                         for j in range(i*i,n,i):
   
7.                                 primes[j] = False
   
8.         primelist = []
   
9.         for (k,trueprime) in enumerate(primes):
   
10.                 if trueprime:
    
11.                         primelist.append(k)
    
12.         return primelist
    
13. primelist = getPrimes(7100)
    
14. 
    
15. xlist = getPrimes(90)
    
16. ylist = getPrimes(380)
    
17. count = []
    
18. for x in xlist:
    
19.         if x**4 >= 50000000:
    
20.                 break
    
21.         for y in ylist:
    
22.                 if x**4 + y**3 >= 50000000:
    
23.                         break
    
24.                 for z in primelist:
    
25.                         n = x**4 + y**3 + z**2
    
26.                         if n >= 50000000:
    
27.                                 break
    
28.                         else:
    
29.                                 count.append(n)
    
30. print len(set(count))
    

复制代码

芒果加黄桃

1. # encoding:utf-8
   
2. # 立方体表面最短路径
   
3. from time import time
   
4. def getPrimes(n):
   
5.         primes = [True] * n
   
6.         primes[0], primes[1] = False, False
   
7.         for (i, prime) in enumerate(primes):
   
8.             if prime:
   
9.                 for j in range(i * i, n, i):
   
10.                     primes[j] = False
    
11.         return [k for (k, v) in enumerate(primes) if v]
    
12. def euler087(N=10000):
    
13.     NN = 50000000
    
14.     l_primes = getPrimes(N)
    
15.     s_result = set()
    
16.     l2 = [x ** 2 for x in l_primes if x <= NN ** (1 / 2)]
    
17.     l3 = [x ** 3 for x in l_primes if x <= NN ** (1 / 3)]
    
18.     l4 = [x ** 4 for x in l_primes if x <= NN ** (1 / 4)]
    
19.     for i in l2:
    
20.         for j in l3:
    
21.             for k in l4:
    
22.                 if i + j + k < NN:
    
23.                     # print(i,j,k)
    
24.                     s_result.add(i + j + k)
    
25.                 else:
    
26.                     break
    
27.     print(len(s_result))
    
28. if __name__ == '__main__':
    
29.     start = time()
    
30.     euler087()
    
31.     print('cost %.6f sec' % (time() - start))
    

复制代码

1097343
cost 0.688068 sec

永恒的蓝色梦想

1. from time import process_time as t
   
2. t1=t()
   
3. def makeprimelist(end):
   
4.   primelist=[True]*(end+1)
   
5.   primelist[0],primelist[1]=None,False
   
6.   for i,prime in enumerate(primelist[:int(end/2)]):
   
7.     if prime:
   
8.       for j in range(2*i,end+1,i):primelist[j]=False
   
9.   return [i for i,prime in enumerate(primelist) if prime]
   
10. aset=set()
    
11. for power4 in makeprimelist(84):
    
12.   for power3 in makeprimelist(368):
    
13.     for power in makeprimelist(7071):
    
14.       num=power**2+power3**3+power4**4
    
15.       if num>50000000:break
    
16.       aset.add(num)
    
17. print('运行结果：{}\n运行时间：{}s'.format(len(aset),t()-t1))

复制代码

运行结果：1097343
运行时间：10.5s

debuggerzh

1097343
欧拉筛+三重循环+集合去重

1. #include <iostream>
   
2. #include <cstdio>
   
3. #include <set>
   
4. #include <cmath>
   
5. using namespace std;
   
6. 
   
7. const int M = 10000;
   
8. const int UB = 5e7;
   
9. 
   
10. bool prime[M + 5];
    
11. int factor[M];
    
12. int kount = 0;
    
13. 
    
14. void euler_sieve()
    
15. {
    
16.     prime[1] = false;
    
17.    
    
18.     for (int i = 2; i <= M; i++)
    
19.         prime[i] = true;
    
20. 
    
21.     for (int i = 2; i <= M; i++)
    
22.     {
    
23.         if (prime[i])
    
24.             factor[++kount] = i;
    
25.         for (int j = 1; j <= kount && i * factor[j] <= M; j++)
    
26.         {
    
27.             prime[i * factor[j]] = false;
    
28.             if (i % factor[j] == 0)
    
29.                 break;
    
30.         }
    
31.     }
    
32. }
    
33. 
    
34. int main(int argc, char const *argv[])
    
35. {
    
36.     //freopen("i.in", "r", stdin);
    
37.     euler_sieve();
    
38.     set<int> sumset;
    
39. 
    
40.     for (int i = 1; i <= kount; i++){
    
41.         int sq = factor[i]*factor[i];
    
42.         if (sq >= UB)   break;
    
43.         for (int j = 1; j <= kount; j++){
    
44.             int cube = factor[j]*factor[j]*factor[j];
    
45.             if (sq + cube >= UB)    break;
    
46.             for (int k = 1; k <= kount; k++){
    
47.                 int pw4 = factor[k]*factor[k]*factor[k]*factor[k];
    
48.                 if (sq + cube + pw4 < UB)   sumset.insert(sq + cube + pw4);
    
49.                 else    break;
    
50.             }
    
51.         }
    
52.     }
    
53.     int ans = sumset.size();
    
54.     cout << ans << endl;
    
55.     return 0;
    
56. }

复制代码

guosl

1. /*
   
2. 答案：1097343
   
3. 耗时：0.572562秒
   
4. */
   
5. #include <iostream>
   
6. #include <cstring>
   
7. #include <algorithm>
   
8. #include <vector>
   
9. using namespace std;
   
10. 
    
11. const int N = 50000000;
    
12. char cp[N];
    
13. vector<int> v2, v3, v4, v34;
    
14. 
    
15. int main(void)
    
16. {
    
17.   memset(cp + 2, 1, (N - 2) * sizeof(char));
    
18.   for (int i = 2; i <= (int)sqrt((double)N); ++i)
    
19.   {
    
20.     if (cp[i] == 0)
    
21.       continue;
    
22.     for (int j = i * i; j < N; j += i)
    
23.       cp[j] = 0;
    
24.   }
    
25.   for (int i = 2; i <= (int)sqrt((double)N); ++i)
    
26.   {
    
27.     if (cp[i] == 0)
    
28.       continue;
    
29.     long long j = i;
    
30.     j *= i;
    
31.     if (j >= N)
    
32.       break;
    
33.     else
    
34.     {
    
35.       v2.push_back(j);
    
36.       j *= i;
    
37.       if (j < N)
    
38.       {
    
39.         v3.push_back(j);
    
40.         j *= i;
    
41.         if (j < N)
    
42.           v4.push_back(j);
    
43.       }
    
44.     }
    
45.   }
    
46.   for (int i = 0; i < (int)v3.size(); ++i)
    
47.   {
    
48.     for (int j = 0; j < (int)v4.size(); ++j)
    
49.     {
    
50.       if (v3[i] + v4[j] >= N)
    
51.         break;
    
52.       v34.push_back(v3[i] + v4[j]);
    
53.     }
    
54.   }
    
55.   v3.clear();
    
56.   sort(v34.begin(), v34.end());
    
57.   auto itr = unique(v34.begin(), v34.end());
    
58.   int n = int(itr - v34.begin());
    
59.   v34.resize(n);
    
60.   for (int i = 0; i < (int)v2.size(); ++i)
    
61.   {
    
62.     for (int j = 0; j < (int)v34.size(); ++j)
    
63.     {
    
64.       if (v2[i] + v34[j] >= N)
    
65.         break;
    
66.       v3.push_back(v2[i] + v34[j]);
    
67.     }
    
68.   }
    
69.   sort(v3.begin(), v3.end());
    
70.   itr = unique(v3.begin(), v3.end());
    
71.   int nCount = 0;
    
72.   for (int i = 28; i < N; ++i)
    
73.   {
    
74.     if (binary_search(v3.begin(), itr, i))
    
75.       ++nCount;
    
76.   }
    
77.   cout << nCount << endl;
    
78.   return 0;
    
79. }
    

复制代码