关于大整数的高效算法

正整数1到n连续排列组成的大整数，计算n最小为多少时，它是1到20的倍数。
大整数结构如下：
12345678910111213141516…99100101102…


   public static void main(String[] args) {
        long l = System.currentTimeMillis();
        System.out.println(l);
        BigInteger start=new BigInteger("1") ;
        BigInteger step=new BigInteger("1") ;
        BigInteger nuber=BigInteger.ONE;
        BigInteger bit=BigInteger.TEN;

        while (true){
            start=start.add(BigInteger.ONE);
            if (check(nuber= nuber.multiply(bit.pow(start.add(step).toString().length())).add(start))){
                System.out.println(start);
                System.out.println(nuber);
                break;
            }
        }
        System.out.println(System.currentTimeMillis()-l);
    }
    private static boolean check(BigInteger start) {

        if (start.remainder(BigInteger.valueOf(20)).compareTo(BigInteger.ZERO)!=0) return false;
        for (int i = 11; i<20; i++) {
            if (start.remainder(BigInteger.valueOf(i)).compareTo(BigInteger.ZERO)!=0) {
                return false;
            }
        }
        return true;
    }

这好像跟高效不太沾边……
也许可以把1-20处理一下只要其中的素数。
写出来了，但是跑不出来，小水管，扛不住

大整数的计算效率是很低的。所以，这条路走不通。大整数计算可以用来检验现成的答案。
受网友提示启发，用余数定理。
在不断增加n，构建大整数的过程中，计算大整数除以1到20的余数，保存在数组中。
这样就可以在 integer4 的范围内通过前一次余数A来求得新余数A1：
A1 = (A10^k+n) mod B
k 是 n 的位数，B 是11到20，因为能被11到20整除，必能被1到10整除。
如果 integer4 出现溢出，就改用 integer8。实际计算结果证明，计算过程没有超出 integer*4 范围。

下面是 fortran代码和计算结果。
n = 210101040
len = 1779798258，这是大整数的位数
time = 12628 ms

img

img

再次进行了优化，通过两层循环，将整数位数计算的环节省略了。耗时缩短到6秒。

img

img