21亿以内的自守数–Java求解

为什么是21亿以内？

java中long最大数是 9223372036854775807，开方大约是30亿，那我们就求21亿以内的自守数，防止在计算过程中出现溢出的现象。作者初学java，就不去求解更大范围的自守数了。

什么是自守数—这里就不多赘述了。

自守数是指某个数的平方的末尾几位数等于这个数的数。

直接贴出答案

0 1 5 6 25 76 376 625 9376 90625 109376 890625 2890625 7109376 12890625 87109376 212890625 787109376已验证 1787109376已验证 之前在网上找结果，想验证自己求10000以内自守数是不是正确，到处找不到答案。欢迎大家来验证。

代码：

public static void main(String[] args) { for (int i = 0; i < 2100000000; i++) //i不要超过21亿， { long lng = (long)i * i; //i平方是long类型，不会超过long最大，不会溢出（30亿会溢出long类型） long mod = lng % getUp(i); if (i == mod) //i会自动提升为long作比较 { System.out.println(i); } } //验证1787109376 // long lng = (long)1787109376 * 1787109376; // System.out.println(lng);//3193759921787109376 } //方法,输入int n ，返回它的上级（最大情况100亿，所以使用long） //此方法为了求得一个数的上一级别数，比如传入一个两位数（如43），返回100。2566返回10000，一次类推 //该方法方便main中“求末尾数”。 public static long getUp(int n) { long d = 1; //容器，初始为1.每次n除以10，d都会增加10倍，n==0时，d就是10,100,1000，.....类推 while (n != 0) { n /= 10; d *= 10; } return d; }

关于运行时间，能不能更优化？

上述代码运行时间挺久，大概10秒（没验证具体时间，有兴趣可以自己验证，和简单，只要3行代码）

如何提高效率呢？我们根据运行结果，查找规律。发现结果后3位不是625就是376.具体原因涉及到数学方面，我也不懂。 我们可以在循环体中加入一定条件，先判断i是不是625 或者 376 结尾？提高代码效率。

int m = i % 1000; if (m != 625 && m != 376) { continue; }

当然这次运行结果会不显示前面的几个自守数，但运行时间确实很短。其实按照这个思路，还能更优化，将i分组，就能在显示全部结果的情况下，时间再次缩短。可以自己尝试。