java - 找到最大 X 的素数 - 复杂性

Question

这个算法需要创建一个大小为 X 的数组，然后每个不是素数的数字在他的索引中输入零。有人可以告诉我复杂度是多少吗？为什么？

    // x is the number we want all the primes below him
    int[] p = new int[x + 1];

    // Initializes the array.
    for (int i = 2; i < p.length; i++) {
        p[i] = i;
    }

    // "Erases" the composite (non-prime) numbers.
    for (int i = 2; i <= Math.sqrt(x); i++) {
        for (int j = i * 2; j < p.length; j += i) {
            p[j] = 0;
        }
    }

复杂度是 O(x*sqrt(x)) 吗？

Answer 1

If you are using the following code, the time complexity is O(x √x).

int[] p = new int[x];
for (int i = 0; i < p.length; i++) {
    p[i] = i+1;
}
for (int i = 4; i <= p.length; i++) {
    for(int j = 2; j <= Math.sqrt(i) ; j += 1) {
        if(i%j==0) {
            p[i-1] = 0;
        }
    }
}