java - 如何优化Java中计算Pronic数的解决方案

Question

最近，在其中一项评估中，我遇到了这个问题:
给定两个整数 A 和 B，返回范围 A..B 中的整数个数，它可以表示为两个连续整数的乘积，即 X *(X + 1)，也称为 Pronic Number。
示例 1:
A = 6 和 B = 20，函数应该返回 3，这些整数是 6 = 2 * 3, 12 = 3 * 4 和 20 = 4* 5
示例 2:
A = 21 和 B = 29，函数应该返回 0
假设:

A 和 B 是 [1...1000,000,000] 范围内的整数

A <= B

我的解决方案对于 1000,000,000 的极端输入失败。我收到超出时间限制的错误。
有人可以帮我进一步优化我的代码吗？

    // Java program to check if a number is pronic or not 

import java.io.*; 
import java.util.*; 
import java.math.*; 

class solution 
{ 

    // Function to check Pronic Number 
    static int pronic_check(int A, int B) 
    { 
        int count = 0;
        for (int i = A; i <= B; i++){
            if (i % 2 == 0)      // a pronic number is always even
            {
                int x = (int)(Math.sqrt(i));
                if (x * (x + 1) == i) 
                    count++; 
            }
        }

        return count;
    } 
    
    public static void main(String[] args) 
    {    
        System.out.println(pronic_check(5000, 990000000));
    } 
} 

提前致谢。

Answer 1

如果你只需要计数。我想这对你来说是最好的。
说明:
让我们假设，A=6 B=20 .
现在，start=sqrt(A)= 2和 end = sqrt(20) = 4 .最初 count = (end-start-1) .在这里，您只需要检查 start和 end .如 (end*(end+1))<= B然后只需增加count由一个。还要检查是否 (start*(start+1) >= A)然后增加count由一个。所以，这里是 count = 3 .
在这里时间复杂度将保持不变 O(1) .

import java.io.*; 
import java.util.*; 
import java.lang.Math; 

class solution 
{ 
   // Function to check Pronic Number 
    static int pronic_check(int A, int B) 
    { 
        int count = 0;
        int start =  (int) Math.sqrt(A); 
        int end = (int) Math.sqrt(B);
        count = (end -start -1 );
        if (start*(start+1) >= A) {
            count++;
        }
        if (end*(end+1) <= B){
            count++;
        } 

        return count;
    } 
    
    public static void main(String[] args) 
    {    
        System.out.println(pronic_check(5000, 990000000));
    } 
}