欧拉计划 发表于 2016-8-10 17:49:55

题目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 发表于 2016-10-17 15:17:04

本帖最后由 jerryxjr1220 于 2016-10-17 15:21 编辑

1097343

def getPrimes(n):
        primes = *n
        primes, primes = False, False
        for (i,prime) in enumerate(primes):
                if prime:
                        for j in range(i*i,n,i):
                                primes = 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))

芒果加黄桃 发表于 2017-2-28 16:32:25

# encoding:utf-8
# 立方体表面最短路径
from time import time
def getPrimes(n):
      primes = * n
      primes, primes = False, False
      for (i, prime) in enumerate(primes):
            if prime:
                for j in range(i * i, n, i):
                  primes = False
      return
def euler087(N=10000):
    NN = 50000000
    l_primes = getPrimes(N)
    s_result = set()
    l2 =
    l3 =
    l4 =
    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

永恒的蓝色梦想 发表于 2019-7-22 00:30:53

from time import process_time as t
t1=t()
def makeprimelist(end):
primelist=*(end+1)
primelist,primelist=None,False
for i,prime in enumerate(primelist[:int(end/2)]):
    if prime:
      for j in range(2*i,end+1,i):primelist=False
return
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 发表于 2021-7-21 09:28:04

1097343
欧拉筛+三重循环+集合去重
#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>
using namespace std;

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

bool prime;
int factor;
int kount = 0;

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

    for (int i = 2; i <= M; i++)
    {
      if (prime)
            factor[++kount] = i;
      for (int j = 1; j <= kount && i * factor <= M; j++)
      {
            prime] = false;
            if (i % factor == 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*factor;
      if (sq >= UB)   break;
      for (int j = 1; j <= kount; j++){
            int cube = factor*factor*factor;
            if (sq + cube >= UB)    break;
            for (int k = 1; k <= kount; k++){
                int pw4 = factor*factor*factor*factor;
                if (sq + cube + pw4 < UB)   sumset.insert(sq + cube + pw4);
                else    break;
            }
      }
    }
    int ans = sumset.size();
    cout << ans << endl;
    return 0;
}

guosl 发表于 2022-1-15 19:24:31

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

const int N = 50000000;
char cp;
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 == 0)
      continue;
    for (int j = i * i; j < N; j += i)
      cp = 0;
}
for (int i = 2; i <= (int)sqrt((double)N); ++i)
{
    if (cp == 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 + v4 >= N)
      break;
      v34.push_back(v3 + v4);
    }
}
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 + v34 >= N)
      break;
      v3.push_back(v2 + v34);
    }
}
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;
}
页: [1]
查看完整版本: 题目87：考察能写成质数的2次，3次和4次方之和的数