关于sqrt优化时间复杂度的问题

Question

问一下这个sqrt优化应该怎么弄
问题：
输入两个正整数m和n，计算其间的所有素数的个数。

输入
输入数据只有一组，在一行上输入两个正整数m和n（1<m，n<=1000000）。提示：当m,n很大时，常规算法可能会超时，请使用sqrtf()予以优化，降低时间复杂度。,例如sqrtf(i)，头文件math.h
输出
在一行上输出m和n之间（包括m和n）的素数的个数。
难度
中等
输入示例

2 10

输出示例

4

Answer 1

供参考：

#include <stdio.h>
int isPrime(int n)
{
    int i;
    if (n <= 3) return n > 1;
    for (i = 2;i * i <= n; i++)
        if (n % i == 0) return 0;
    return 1;
}
int main()
{
    int m,n,cnt=0;
    scanf("%d%d", &m, &n);
    for (m; m <= n; m++)
    {
        if (isPrime(m)) cnt++;
    }
    printf("%d", cnt);
    return 0;
}