We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #87: Prime power triples
  4. Discussions

Project Euler #87: Prime power triples

Sort by

recency

|

16 Discussions

|

  • xZero
     + 0 comments

    Python 3: Passed all the tests

    import math
import bisect
big_N = 10**7
N = 3164 #sqrt(10**7)
Primes = [True]*N
for i in range(2, int(N**0.5)):
    if Primes[i] == True:
        for j in range(i * i, int(N), i):
            Primes[j] = False
Primes[0] = Primes[1] = False
sum_list = set()

for i in range(2, math.ceil(math.sqrt(big_N))):
    for j in range(2, math.ceil(big_N ** (1/3))):
        for k in range(2, math.ceil(big_N ** (1/4))):
            if Primes[i] and Primes[j] and Primes[k]:
                # print(i, j, k)
                Sum = i**2 + j**3 + k**4
                if Sum > big_N:
                    break
                sum_list.add(Sum) 
sums = list(sum_list)
sums.sort()

for i in range(int(input())):
    n = int(input())
    print(bisect.bisect_right(sums, n))

  • leduckhai
     + 0 comments

    Hint: this problem works with brute-force. Run 3 loops for i in (1:3163), for j in (1:216), and for k in (1:57)

  • julien_bourgoui1
     + 0 comments

    Hello everyone, Nice problem and good job for hackerrank but like euler problems I solved before, I spent basically 30 minutes getting an answer to the Euler problem + 30 minutes figuring out how to handle the many test cases (i.e, my code works for T = 1 and N = 50 * 10 ** 7, let's make it work for large T and N = 10 ** 7).

    What do you think of that feature for hackerrank problem (making you think on how to handle a large number of cases) ?

    Is it a necessary evil so that cheater / people who program something not generic enough can't solve the problem and get the 100 points ? is it a good thing to enhance one's programming skills ? it's just a bad thing ?

  • 206118022_soumya
     + 1 comment

    this is my code... it ran fine upto 10^8 on codechef. don't knw why hackerrank can't run it after around 835000... pls help

    #include <bits/stdc++.h>

using namespace std;

inline long long pow2(long long a){return a*a;}
inline long long pow3(long long a){return a*a*a;}
inline long long pow4(long long a){return a*a*a*a;}

int main() {
    long t;
    cin >> t;
    long mx = -1;
    long a[t];
    for(long i = 0; i < t; i++){
        cin >> a[i];
        if(a[i] > mx) mx = a[i];
    }

    int b[mx+1];
    for(long i = 0; i < mx+1; i++) b[i] = 0;

    int pr = pow(100000000, 0.5)+1;

    vector<long> primes;
    primes.push_back(2);
    for(int k = 3; k <= pr; k++){
        bool isPrime = true;
        for(auto p : primes){
            if(k % p == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) primes.push_back(k);
    }

    int x = primes.size();

    long long sum = 0;
    for(int i = 0; i < x; i++){
        sum = 0;
        sum += pow4(primes[i]);
        if(sum > mx){
            sum -= pow4(primes[i]);
            break;
        }
        for(int j = 0; j < x; j++){
            sum += pow3(primes[j]);
            if(sum > mx){
                sum -= pow3(primes[j]);
                break;
            }
            for(int k = 0; k < x; k++){
                sum += pow2(primes[k]);
                //cout << sum << endl;
                if(sum > mx){
                    sum -= pow2(primes[k]);
                    break;
                }
                b[sum] = 1;
                sum -= pow2(primes[k]);
            }
            sum -= pow3(primes[j]);
        }
        sum -= pow4(primes[i]);
    }

    for(long tt = 0; tt < t; tt++){
        long long res = 0;
        for(long i = 0; i < a[tt]+1; i++) res += b[i];
        cout << res << endl;
    }

    return 0;
}

  • kitchent
     + 0 comments

    Earlier I tried with bisect, ans += index + 1 and then break, but the issue here is with duplicates. It seems all solutions here are sort of brute force with sets to remove duplicates, and it is always ans += 1 in the counting itself. I wonder if there could be any dynamic programming involved in it.