该程序需要大量时间来执行

Question

public class Solution {

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int t = in.nextInt();
    if(t<1 || t>100){System.exit(0);}
    ArrayList a=new ArrayList<>();         
    for(int i=0;i<t;i++){ 
        String s=in.next().toString(); 
        String s2=in.next().toString();      
        int count=0;
        int first=Integer.parseInt(s);
        int last=Integer.parseInt(s2);
        if(first<1 || last>1000000000){System.exit(0);}
        for(int k=first;k<=last;k++){                    
                int sqrt =(int)Math.sqrt(k);
                if(sqrt*sqrt==k){count++;}                                     
        }
        a.add(count);
    }
    Iterator it=a.iterator();
    while(it.hasNext()){
    System.out.println(it.next());
    }        
}
}

在这个程序中,当我提供大量输入时,需要很多时间来提供输出.有人能告诉我如何优化这个程序.该程序用于查找平方根号.输入:第一行包含测试用例的数量T.T测试用例如下,每一行都在一个新行中.每个测试用例包含两个以空格分隔的整数,表示s和s2.

样本输入

2
3 9
17 24

样本输出

2
0

大投入:

35
465868129 988379794
181510012 293922871
395151610 407596310
481403421 520201871
309804254 776824625
304742289 566848910
267554756 828997506
387224568 926504395
244571677 871603971
444567315 582147918
334350264 342469009
400474096 410940967
488907300 943628573
26441071 801576263
182001128 267557939
115732998 974318256
192538332 862327048
45429427 307805497
358658006 842644090
92930998 431601473
231163983 893672132
275221547 298953978
351237326 981399371
484598992 985428966
103405553 529324202
37393469 768655346
30179914 482808626
208821550 538302223
154654533 791652309
68424067 854065374
246956110 517538724
51395253 876949418
57778758 368742600
227566632 606529208

Answer 1

此方法计算两个边界之间的平方数:

public static int squaredNumberInRange(int lowerBound, int upperBound){
    double lowerRoot = Math.sqrt(lowerBound);
    double upperRoot = Math.sqrt(upperBound);

    lowerRoot = Math.ceil(lowerRoot);
    upperRoot = Math.floor(upperRoot);

    int spread = (int)upperRoot - (int)lowerRoot + 1;

    return spread;
}

复杂性是O(1)