algorithm - 确定一个数是否为素数的平均情况（不是使用最优算法）

Question

我有以下函数来确定一个数字是否是素数。我知道最好的时间复杂度是 O((logN)^6) 但下面的算法要简单得多。我也知道它有 O(sqrt(N)) 的最坏情况，我正在尝试考虑它的平均情况复杂性。我需要答案的解释/证明。这是我的功能和测试它的基本程序：

#include <stdio.h>
#include <math.h>
int isprime(int N){
    int j;
    if(N==2){
        return 1;
    }
    for(j=2;j<=ceil(sqrt(N));j++){
        if(N%j==0){
            return 0;//false, number is not prime
        }
    }
    return 1;//true, number is prime
}
int main(){
    int i;
    for(i=2;i<100;i++){
        printf("Number: %d \t %d\n",i,isprime(i));
    }
    return 0;
}

该示例使用 C 语言，但我关心问题的算法部分，因此我没有在标签中包含任何编程语言的名称。

标签： algorithm