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.
Project Euler #29: Distinct powers
Project Euler #29: Distinct powers
Contest ends in
+ 1 comment L=[] N=int(input("")) if N>=2 and N<=10**5: for a in range(2,N+1): for b in range(2,N+1): c=a**b if c not in L: L.append(c) else: pass print(len(L)) else: pass
+ 0 comments I cannot able to understand these problem
+ 0 comments 100/-points python3
no=int(input()) li=[True]*(no+1) answer=0 for i in range(2,no+1): if li[i]: power=2 #this was the last time reducing step for me as for power =1 it gets timeout answers=[] while i**power<=no: li[i**power]=False answers+=[n for n in range(2*power,no*power+1,power) if n>no] power+=1 answer+=len(set(answers))+(no-1) print(answer) #took me 3 days
+ 0 comments And the same code in C++.
#include <cstdio> #include <vector> #include <set> using namespace std; long distinct_powers(long n) { long c = 0; vector<bool> tested(n+1, false); for (long a = 2; a <= n; a++) if (!tested[a]) { set<long> s; for (long _a = a*a, pw = 2; _a <= n; _a *= a, pw++) { tested[_a] = true; for (long b = 2, bxpw = b*pw; b <= n; b++, bxpw += pw) if (bxpw > n) s.insert(bxpw); } c += s.size() + n-1; } return c; } int main() { long n; scanf("%ld", &n); printf("%ld\n", distinct_powers(n)); return 0; }
+ 0 comments This was a bit of a rabbit hole, definitely not an "easy" task. Here's the code. The idea is for each base to iterate through its powers e.g. for 2 iterate through 4, 8, 16, ... . Create a set of exponents for each power e.g. for 8 we have 8^2=2^6, 8^3=2^9, ... and therefore exponents will be 6, 9, .. . Then merge all sets. Don't do sets for the bases though to avoid timeout.
def distinct_terms(n: int) -> int: count = 0 tested = [0]*(n+1) for a in range(2, n+1): if tested[a]: continue; combined = set() pw = 2 while (a**pw <= n): tested[a**pw] = True s = set([b*pw for b in range(2, n+1) if b*pw > n]) combined.update(s) pw += 1 count += len(combined) + n-1 return count print(distinct_terms(int(input())))
Load more conversations
Sort 44 Discussions, By:
Please Login in order to post a comment