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 #64: Odd period square roots
  4. Discussions

Project Euler #64: Odd period square roots

  • sathish126
     + 0 comments

    python3 code 100points/-

    import math

def perf_arc(n):
    root = int(math.sqrt(n))
    if root * root == n:
        return 0
    
    a = 1
    listaint = [root]
    den = n - root * root
    lista_inv_frac = [(math.sqrt(n) + root) / den]
    per = 0
    
    while True:
        part_int = int(lista_inv_frac[-1])
        root = (den * part_int) // a - root
        a = den // a
        den = n - root * root
        invfrac = a * (math.sqrt(n) + root) / den
        listaint.append(part_int)
        lista_inv_frac.append(invfrac)
        per += 1
        
        if invfrac == lista_inv_frac[0]:
            return per

def main():
    n = int(input())
    cnt_odd = 0
    
    for k in range(2, n + 1):
        if perf_arc(k) % 2 == 1:
            cnt_odd += 1
    
    print(cnt_odd)

if __name__ == "__main__":
    main()