给出筛法求整数区间[m,n]的c语言代码，并通过查阅相关资料说明其时间复杂度

筛法求整数区间[m,n]的C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

void sieve(int m, int n) {
    bool *is_prime = (bool*)malloc((n+1) * sizeof(bool));
    for (int i = 2; i <= n; i++) {
        is_prime[i] = true;
    }
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }
    for (int i = m; i <= n; i++) {
        if (is_prime[i]) {
            printf("%d ", i);
        }
    }
    free(is_prime);
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    sieve(m, n);
    return ;
}

时间复杂度：O(nloglogn)

筛法的时间复杂度与素数个数有关，而素数个数不超过n/logn，因此时间复杂度为O(nloglogn)。