C Homework 2.2 - Prime 质数

博主：枫亚
发布时间：2021 年 10 月 21 日
547 次浏览
暂无评论
576字数
分类：杂谈

# Assignment 2.2 - Prime 质数

## 功能

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

## 输入输出

输入：$n$

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

## 实现

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

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

## 生成

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

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

```shell
mkdir build
cmake ..
make
./prime
```

## 代码

```c
#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;
}
```

最后修改：2021 年 10 月 22 日