题目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]

def getPrimes(n):
        primes = [True]*n
        primes[0], primes[1] = False, False
        for (i,prime) in enumerate(primes):
                if prime:
                        for j in range(i*i,n,i):
                                primes[j] = False
        primelist = []
        for (k,trueprime) in enumerate(primes):
                if trueprime:
                        primelist.append(k)
        return primelist
primelist = getPrimes(7100)

xlist = getPrimes(90)
ylist = getPrimes(380)
count = []
for x in xlist:
        if x**4 >= 50000000:
                break
        for y in ylist:
                if x**4 + y**3 >= 50000000:
                        break
                for z in primelist:
                        n = x**4 + y**3 + z**2
                        if n >= 50000000:
                                break
                        else:
                                count.append(n)
print len(set(count))

芒果加黄桃

# encoding:utf-8
# 立方体表面最短路径
from time import time
def getPrimes(n):
        primes = [True] * n
        primes[0], primes[1] = False, False
        for (i, prime) in enumerate(primes):
            if prime:
                for j in range(i * i, n, i): 
                    primes[j] = False
        return [k for (k, v) in enumerate(primes) if v]
def euler087(N=10000):
    NN = 50000000
    l_primes = getPrimes(N)
    s_result = set()
    l2 = [x ** 2 for x in l_primes if x <= NN ** (1 / 2)]
    l3 = [x ** 3 for x in l_primes if x <= NN ** (1 / 3)]
    l4 = [x ** 4 for x in l_primes if x <= NN ** (1 / 4)]
    for i in l2:
        for j in l3:
            for k in l4:
                if i + j + k < NN:
                    # print(i,j,k)
                    s_result.add(i + j + k)
                else:
                    break
    print(len(s_result))
if __name__ == '__main__':
    start = time() 
    euler087()
    print('cost %.6f sec' % (time() - start))

1097343
cost 0.688068 sec

永恒的蓝色梦想

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

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

debuggerzh

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

#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>
using namespace std;

const int M = 10000;
const int UB = 5e7;

bool prime[M + 5];
int factor[M];
int kount = 0;

void euler_sieve()
{
    prime[1] = false;
    
    for (int i = 2; i <= M; i++)
        prime[i] = true;

    for (int i = 2; i <= M; i++)
    {
        if (prime[i])
            factor[++kount] = i;
        for (int j = 1; j <= kount && i * factor[j] <= M; j++)
        {
            prime[i * factor[j]] = false;
            if (i % factor[j] == 0)
                break;
        }
    }
}

int main(int argc, char const *argv[])
{
    //freopen("i.in", "r", stdin);
    euler_sieve();
    set<int> sumset;

    for (int i = 1; i <= kount; i++){
        int sq = factor[i]*factor[i];
        if (sq >= UB)   break;
        for (int j = 1; j <= kount; j++){
            int cube = factor[j]*factor[j]*factor[j];
            if (sq + cube >= UB)    break; 
            for (int k = 1; k <= kount; k++){
                int pw4 = factor[k]*factor[k]*factor[k]*factor[k];
                if (sq + cube + pw4 < UB)   sumset.insert(sq + cube + pw4);
                else    break;
            }
        }
    }
    int ans = sumset.size();
    cout << ans << endl;
    return 0;
}

guosl

/*
答案：1097343
耗时：0.572562秒
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 50000000;
char cp[N];
vector<int> v2, v3, v4, v34;

int main(void)
{
  memset(cp + 2, 1, (N - 2) * sizeof(char));
  for (int i = 2; i <= (int)sqrt((double)N); ++i)
  {
    if (cp[i] == 0)
      continue;
    for (int j = i * i; j < N; j += i)
      cp[j] = 0;
  }
  for (int i = 2; i <= (int)sqrt((double)N); ++i)
  {
    if (cp[i] == 0)
      continue;
    long long j = i;
    j *= i;
    if (j >= N)
      break;
    else
    {
      v2.push_back(j);
      j *= i;
      if (j < N)
      {
        v3.push_back(j);
        j *= i;
        if (j < N)
          v4.push_back(j);
      }
    }
  }
  for (int i = 0; i < (int)v3.size(); ++i)
  {
    for (int j = 0; j < (int)v4.size(); ++j)
    {
      if (v3[i] + v4[j] >= N)
        break;
      v34.push_back(v3[i] + v4[j]);
    }
  }
  v3.clear();
  sort(v34.begin(), v34.end());
  auto itr = unique(v34.begin(), v34.end());
  int n = int(itr - v34.begin());
  v34.resize(n);
  for (int i = 0; i < (int)v2.size(); ++i)
  {
    for (int j = 0; j < (int)v34.size(); ++j)
    {
      if (v2[i] + v34[j] >= N)
        break;
      v3.push_back(v2[i] + v34[j]);
    }
  }
  sort(v3.begin(), v3.end());
  itr = unique(v3.begin(), v3.end());
  int nCount = 0;
  for (int i = 28; i < N; ++i)
  {
    if (binary_search(v3.begin(), itr, i))
      ++nCount;
  }
  cout << nCount << endl;
  return 0;
}