厄拉托塞师筛法

题目描述

编程实现厄拉托塞师筛法的算法，求出10000以内的全部素数

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main() {
    long n;
    printf("Please enter a integer for the upper bound: ");
    scanf("%ld", &n);

    //标记数据，1代表素数，0代表非素数
    int *isPrime;   
    isPrime = (int *)malloc(sizeof(long) * (n + 1));
    isPrime[0] = 0;  //0不是素数 
    isPrime[1] = 0;  //1不是素数 
    long i, j;
    for (i = 2; i <= n; i++) {
        isPrime[i] = 1;  //初始化，假定2~n都是素数，均标记为1 
    }
    for (i = 2; i <= (long)sqrt(n); i++) {
        if(isPrime[i] == 1) {
            for (j = i; j * i <= n; j++) {
                isPrime[j*i] = 0;   //筛去素数的倍数 
            }
        }
    }

    long count = 0;    //记录素数的总数 
    for (i = 2; i <= n; i++) {
        if(isPrime[i] == 1) {
            count++;
            printf("%8d", i);  //输出 
        }
    }
    printf("\nThe total number of primes from 0 to %ld is %ld\n", n, count);
    return 0;
}