欧拉工程第64题：Odd period square roots

题目链接

找循环位数是奇数的数有多少个

这个自己很难写出来，完全不能暴力

维基百科链接 维基百科上面说的很好，上面的算法实现就好了。

就是上面的

Java程序：

package project61;

public class P64{

    void run(){

        int count = 0;

        int m = 0;

        int d = 1;

        int a0 = 0;

        int a = 0;

        int period = 0;

        for(int S = 2;S<10000;S++){

            period = 0;

            m = 0;

            d = 1;

            a0 = (int) (Math.sqrt(S));

            if(a0*a0 == S) continue;

            a = a0;

            do{

                m = d*a - m;

                d = (S-m*m)/d;

                a = (a0+m)/d;

                period++;

            }while(a!=2*a0);

            if(period%2==1) count++;

        }

        System.out.println(count);

    }

    public static void main(String[] args){

        long  start = System.currentTimeMillis();

        new P64().run();

        long end = System.currentTimeMillis();

        long time =end - start;

        System.out.println("run time:"+ time/1000+"s"+time%1000+"ms");

    }

}

Python程序

import time as time

start = time.time()

count  = 0

for S in range(2,10000):

    m = 0

    d = 1

    a0 = int(S**0.5)

    if a0*a0 == S :continue

    preiod = 0

    a= a0

    while a!=2*a0:

        m = d*a - m

        d = (S - m*m)/d

        a = int((a0 + m)/d)

        preiod+=1

    if preiod%2==1:count +=1

end = time.time()

print "time={0} secs,count={1}".format((end-start),count)

上面两个程序几乎一样的