C 练习实例36 - 求100之内的素数

参考方法：

#include <stdio.h>
#define N 101

int prime[N],pNum=0;
int p[N]={0};   //0表示为素数，1表示为非素数

void Find_Prime(){
    int i,j;
    for(i=2;i<N;i++){
        if(p[i]==0){
            prime[pNum++]=i;
            //埃氏筛法
            for(j=i+i;j<N;j+=i)
                p[j]=1;
        }
    }
}

int main(){
    Find_Prime();
    int i;
    for(i=0;i<pNum;i++){
        printf("%d ",prime[i]);
    }
    return 0;
}

参考方法：

//使用数组存储已经获得的素数，使用该数组做为底，当取值范围较大时可有效减少运算量
#include<stdio.h> 

int main()
{
    int i,j,k=0,n;    //k为素数数组的下标
    int prime[1000];   //建立一个素数数组
    printf("请输入求素数值的范围(0-1000):\n");
    scanf("%d",&n);
    prime[0]=2;       //给第一个数组元素赋值
    for(i=2;i<=n;i++)
    {
        for(j=0;j<=k;j++)  
        {
            if(i%prime[j]==0) //求余比较只要对当前的素数数组求余即可
                break;
        }
        if(j>k)
        {
            k++;                //判断i是否为素数，如果是，将其加入数组，下标k加一
            prime[k]=i;
        }   
    } 
    for(i=0;i<=k;i++) 
        printf("%d  ",prime[i]);
}

参考方案：

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include <stdlib.h>
#include <sys/time.h>

//素数判定 筛选法
int main(){
    int num = 100;
    int i, j;
    //scanf("%d", &num);
    //getchar();
    bool *b;
    b=(bool *)calloc(num + 1, sizeof(bool));
    b[0] = false;
    for(i = 1; i <= num; i++){
        if(i % 2 == 0){
           b[i] = false;
        }else{
           b[i] = true;
        }
    }

    for(int i = 3; i <= sqrt(num); i+=2){
        if(b[i]){
            for(j=i+i; j <= num; j+=i)
                b[j] = false;
        }
    }

    
    //输出素数
    printf("2,");    
    for(i = 3; i <= num; i+=2){
       if(b[i]){
           printf("%d,", i);
       }
    }

    free(b);
    b=NULL;
    return 0;
}