如何编写运行时间为O(N½)的确定正整数是否为素数的代码？

Question

如何编写运行时间为O(N½)的确定正整数是否为素数的代码？

Answer 1

供参考：

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;
}