Project Euler #29: Distinct powers Discussions |

rishabhsahlot_rs 6 months ago+ 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)