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;
}