45 lines
1.1 KiB
Python
45 lines
1.1 KiB
Python
# 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:
|
|
#
|
|
# 28 = 22 + 23 + 24
|
|
# 33 = 32 + 23 + 24
|
|
# 49 = 52 + 23 + 24
|
|
# 47 = 22 + 33 + 24
|
|
#
|
|
# How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?
|
|
|
|
from numpy import zeros
|
|
|
|
from projecteuler import sieve, timing
|
|
|
|
|
|
@timing
|
|
def p087():
|
|
N = 50000000
|
|
SQRT_N = 7071
|
|
RAD3_N = 368
|
|
RAD4_N = 84
|
|
|
|
primes = sieve(SQRT_N + 1)
|
|
numbers = zeros(N)
|
|
count = 0
|
|
|
|
for i in range(2, SQRT_N + 1):
|
|
if primes[i]:
|
|
for j in range(2, RAD3_N + 1):
|
|
if primes[j]:
|
|
for k in range(2, RAD4_N + 1):
|
|
if primes[k]:
|
|
n = i ** 2 + j ** 3 + k ** 4
|
|
|
|
if n < N and numbers[n] == 0:
|
|
count += 1
|
|
numbers[n] = 1
|
|
|
|
print('Project Euler, Problem 87')
|
|
print(f'Answer: {count}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p087()
|