algorithm - 检查数字是否为素数的算法的时间复杂度是多少？

Question

我需要找出检查整数是否为素数的算法的时间复杂度是多少？这个算法有点不同，因为它使用一个 while 循环来完成它的任务

这是 Java 中的方法:

    public static boolean isPrime(int num) {
        int i = 2;
        boolean isPrime = false;

        while(num % i != 0) {
            i += 1;
        }

        if (num == i) {
            isPrime = true;
        }

        return isPrime;
    }

对于 while 循环，我有一个比较，我在循环外有一个 if 语句，if 语句将始终运行一次，所以 O(1)。现在 while 循环的大 O 是什么？是 O(n) 吗？

Answer 1

您的方法可能有一些小问题(在下面解决)，但您的方法应该是 O(n)，其中 n 是输入的值/大小isPrime()。也就是说，在这种蛮力方法中，您基本上只是循环遍历小于输入的每个可能值以找到精确匹配。

我会重写为:

// assuming positive integers only
public static boolean isPrime(int num) {
    if (num == 1) return false;

    boolean isPrime = true;

    for (int i=2; i < Math.sqrt(num); ++i) {
        if (num % i == 0) {
            isPrime = false;
            break;
        }

    return isPrime;
}

我检查输入是否为 1，在这种情况下它不是素数。此外，这种方法还有一个额外的好处，即它最多只检查 sqrt(num) 的可能除数。任何大于该数的除数都不可能被整除，因此检查没有意义。如果我们找到一个除数，我们就会从 for 循环中跳出。