#include <stdio.h>
#include <stdlib.h>
/*
首先将2到n范围内的整数写下来,其中2是最小的素数。
所以2的倍数一定是合数,将表中所有的2的倍数划去。
剩下的数里最小的数也是质数,以此类推划掉该质数的倍数。
划完全部的数,剩下的就是质数。
时间复杂度是O(nloglogn)。
*/
void eratosthenes(int *nums, int numsSize) {
for (int i = 2; i < numsSize; i++) {
if (nums[i]) {
for (int j = 2; i * j < numsSize; j++) {
nums[i * j] = 0;
}
}
}
}
int main() {
int n;
scanf("%d", &n);
if (n < 2) return 0; //如果小于2,代表没有质数直接返回
n++; //0~n有n+1个数,所以数组大小加1
int *nums = (int *) malloc(sizeof(int) * (n));//动态开辟数组
nums[0] = nums[1] = 0; //0 和 1 不是质数
// 给数组赋初值,假设后面的都是质数,1为质数,0为非质数
for (int i = 2; i < n; i++) {
nums[i] = 1;
}
//进行埃氏筛法
eratosthenes(nums, n);
//遍历数组将是质数的给打印
for (int i = 2; i < n; i++) {
if (nums[i]) {
printf("%d ", i);
}
}
return 0;
}