判断素数 -- 暴力算法和埃筛法

程序执行结果：

实现代码：

#include <stdbool.h>
#include <string.h>
#include <stdio.h>
#define N (max-min)

/* 判断素数--暴力算法 */
bool prime_bf(int n)
{
    int j;
    if(n < 2) return false;

    for(j = 2; j*j <= n; j++)
    {
        //余数为0 说明存在合数j，不是素数，返回false
        if(n % j == 0) return false;
    }
    //不存在合数，为素数，返回true
    return true;
}

/* 判断素数--埃氏筛查法 */
int prime_e(int n)
{
    int i, j, count = 0;
    //默认都是素数
    bool prime[n];
    memset(prime, true, sizeof(prime));

    for(i = 2; i < n; i++)
    {
        if(prime[i])//是素数
        {
            count++;
            for(j = i*i; j < n; j += i)
            {
                //当前素数的倍数不是素数
                prime[j] = false;
            }
        }
    }
    return count;
}

/* 暴力-计数 */
int counts(int n)
{
    int i, j, count = 0;
    for(i = 2; i <= n; i++)
    {
        count += prime_bf(i)?1:0;
    }
    return count;
}

int main()
{
    int n;;
    printf("输入计算范围2-");
    scanf("%d", &n);

    //暴力算法
    int ret1 = counts(n);
    //埃筛法
    int ret2 = prime_e(n);

    printf("暴力算法:2-%d之间的素数个数为: %d\n", n, ret1);
    printf("埃筛  法:2-%d之间的素数个数为: %d\n", n, ret2);
    
    return 0;
}