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 #29: Distinct powers
  4. Discussions

Project Euler #29: Distinct powers

  • rishabhsahlot_rs
     + 0 comments

    I made a list of list factors(1 and the number itself excluded) for each number from 2-N. Then I traversed each number,for all a's where a=2-N, wherein in I excluded all b's(b=2-N) which had atleast 1 factor less than log(N) to the base a.The count of the rest was what I came up with as the final answer.Can anyone suggest where this method goes wrong, with a test case? Thank you 

    import math
n=int(input())
l=list()
for i in range(2,n+1):
    l1=list()
    for j in range(2,int(i**(0.5))+1):
        if(i%j==0):
            if(i//j==j):
                l1.append(j)
            else:
                l1.append(j)
                l1.append(i//j)
    l1.sort()
    l.append(l1)

i=2
ct=0
while i<n+1:
    mx=math.log(n,i)
    if(mx<2):
        break
    for j in range(2,n+1):
        if(len(l[j-2])>0):
            if(l[j-2][0]<=mx):
                ct=ct+1
    i=i+1
print(((n-1)**2)-ct)