Project Euler 64

gistfile1.txt

import math

squares=[]
for i in range (1,10000):
	squares.append(i*i)

def CF_of_sqrt(n):
# modified this from http://eli.thegreenplace.net/2009/06/19/project-euler-problem-66-and-continued-fractions/
# who got it from http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfINTRO.html#sqrtalgsalg
    if n in squares: 
        return [int(math.sqrt(n))]
    ans = []
    step1_num = 0
    step1_denom = 1
    while True:
        nextn = int((math.floor(math.sqrt(n)) + step1_num) / step1_denom)
        ans.append(int(nextn))
        step2_num = step1_denom
        step2_denom = step1_num - step1_denom * nextn
        step3_denom = (n - step2_denom ** 2) / step2_num
        step3_num = -step2_denom
        if step3_denom == 1:
            ans.append(ans[0] * 2)
            break
        step1_num, step1_denom = step3_num, step3_denom
    return ans

count = 0
for j in range (1,10000):
	if len(CF_of_sqrt(j))%2 != True:
		count +=1
print count