14047: 【原4047】埃拉托色尼筛法

题目描述

author: 程序设计思想与方法助教组黄海鑫 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4047

问题描述

``````2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
``````

输入输出描述

输入

• 输入为一个正整数n, 2≤n≤2000000

输出

• 输出为一行，输出所有小于或等于输入的素数
• 数据之间用空格分隔
• 最后的一行输出后面无空格

程序运行示例1

Sample Input 1

``````5
``````

Sample Output 1

``````2 3 5
``````

程序运行示例2

Sample Input 2

``````20
``````

Sample Output 2

``````2 3 5 7 11 13 17 19
``````

注意

• 不要显示多余的提示信息，避免输出判定错误
• 注意判断输出信息是否符合要求。

FineArtz's solution

``````/* 埃拉托色尼筛法 */
#include <iostream>
using namespace std;

bool isp[2000001];

int main(){
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 2; i <= n; ++i){
if (!isp[i]){
cout << i << ' ';
for (int j = i; j <= n; j = j + i){
isp[j] = true;
}
}
}
return 0;
}
``````

ligongzzz's solution

``````#include "iostream"
using namespace std;

int main() {
bool a[2000001];
int num;
cin >> num;

for (int i = 0; i <= num; i++)
a[i] = true;

for (int i = 2; i <= num; i++) {
if (a[i]) {
for (int j = 2; i*j <= num; j++)
a[i*j] = false;
}
}

cout << "2";

for (int i = 3; i <= num; i++) {
if (a[i])
cout << " " << i;
}

return 0;
}
``````

LuminousXLB's solution

``````// 4047. 埃拉托色尼筛法
// #519468 正确 / 分数：100 / 时间：130ms / 内存：14300kb
#include <cstdio>
#include <cmath>

const size_t maxsize = 2000000;

int main(int argc, char const *argv[]) {
bool arr[maxsize] = { 0 };
size_t max;

scanf("%d", &max);
double sup = sqrt(max) + 1;

for (size_t i = 3; i <= sup; i += 2) {
// printf("i = %d flag = %d\n", i, arr[i]);
if (arr[i]) {
continue;
} else {
for (size_t j = 3; i * j <= max; j += 2) {
arr[i * j] = true;
}
}
}

printf("2");
for (size_t i = 3; i <= max; i += 2) {
if (!arr[i]) {
printf(" %d", i);
}
}

return 0;
}
``````

victrid's solution

``````#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
bool *Isprime = new bool[2000001];
bool SPACE_FLAG = false;
Isprime[0] = false;
Isprime[1] = false;

for (int i = 2; i <= n; i++) {
if (!Isprime[i])continue;
for (int j = 2; i * j <= n; j++) {
Isprime[i * j] = false;
}
if (SPACE_FLAG)cout << ' ';
cout << i;
SPACE_FLAG = true;
}
return 0;
}
``````