求Java语言中素数判断程序的Big-O时间复杂度

Hey there! Let's walk through the time complexity of your Java isPrime method and clear up your confusion.

First, let's recap your code for easy reference:

public static boolean isPrime(int k) { 
    if (k <= 1) return false; 
    else if (k > 2 && k%2 == 0) return false; 
    else { 
        for(int i = 3;i<=k/2;i+=2) 
            if (k % i == 0) return false; 
    } 
    return true; 
}

Key Big-O Basics to Remember #

Big-O notation focuses on asymptotic growth—how the algorithm's runtime scales as the input size (here, k) gets extremely large. Constant factors and small fixed-cost operations get ignored because they don't change the core trend of how runtime increases with input size.

Breaking Down Your Method's Complexity #

• The initial checks (k <=1, even number validation) are all O(1) operations—they take a fixed amount of time no matter how big k is.
• The critical piece is the for loop. You guessed the complexity might be n/2, but here's the catch: while the loop runs roughly k/4 times (starting at 3, stepping by 2, stopping at k/2), Big-O ignores constant coefficients. So whether it's k/2 or k/4, both simplify to O(k)—a linear time complexity.

A Quick Optimization Tip #

Just as a bonus: you can make this method way more efficient. Instead of looping up to k/2, you only need to loop up to Math.sqrt(k). Here's why: if k has a factor larger than its square root, its corresponding pair factor will always be smaller than the square root. Changing the loop condition to i <= Math.sqrt(k) drops the time complexity to O(√k), which is drastically faster for large values of k.

内容的提问来源于stack exchange，提问作者Faisal Alzahrani