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;
}
最后修改:2021 年 10 月 22 日 07 : 11 PM
如果觉得这篇文章对你有用,请随意赞赏~