Assignment 2.2 - Prime 质数

功能

输出不大于$n$的所有质数。

输入输出

输入：$n$

输出：不大于$n$的所有质数，以空格分隔，从小到大输出。

实现

从$2$至$n$依次遍历，对于每个被遍历的数$a$，计算$a$是否能被质数表中小于等于$\sqrt a$的质数整除，

若不能，则$a$为质数，加入质数表中。

生成

由于使用了libmath进行开根计算，在gcc编译时需要加入-lm参数。

在CMakeLists.txt中已经进行相关配置，可以通过以下命令进行生成：

mkdir build
cmake ..
make
./prime

代码

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

// long long is too slow
int PrimeList[10000000] = {0};

int isPrime(int a)
{
    int i=0;
    int sqrt_a = sqrt(a);
    while(PrimeList[i] != 0 && PrimeList[i]<= sqrt_a)
    {
        if(a%PrimeList[i] == 0)
            return 0;
        i++;
    }
    return 1;
}

int main()
{
    int indexPrimeList = 0;
    int max = 10000000;
    printf("Input n:\n> ");
    scanf("%d", &max);
    for(int a=2; a<=max; a++)       // ll is too slow
    {
        if(isPrime(a))
        {
            PrimeList[indexPrimeList] = a;
            indexPrimeList++;
        }
    }
    for(int a=0; a<indexPrimeList; a++)
    {
        printf("%d ", PrimeList[a]);
    }
    printf("\n");
    return 0;
}