埃氏筛和欧拉筛...随便搜一下就有原理了
提示：想像将(1, N]的数字看成沙子和小石头，视非素数为沙子，视素数为小石头。将沙子筛走，剩下的就是小石头了。考虑到N最大也就是10000，你可以开一个长度为10000的数组，让数组元素的值作为筛去与否的标志，比如筛去以后让元素值为1，然后依次输出就可以了。当然，如果你有更好的办法，也可以试试哦！
Sample 1
| Inputcopy | Outputcopy |
|---|
8 | 2
3
5
7 |
Sponsor
埃氏筛：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int sum;
bool state[10001];
bool isprime(int k) {
for (int i = 2; i <= sqrt(k); i++) {
if (k % i == 0) return false;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
if (!state[i]) {
if (isprime(i)) {
cout << i << endl;
for (int j = i; j <= n; j += i) {
state[j] == true;
}
}
}
}
return 0;
}
欧拉筛 ：
稍微说一下一个值得注意的地方吧：欧拉筛中出现的素数与素数的乘积，弥补了一些因为线性推进而可能遗漏的地方
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int sum;
bool state[10001];
int prime[10001];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 2; i <= n; i++) {
if (!state[i])
prime[sum++] = i;
for (int j = 0; j < sum; j++) {
if (prime[j] * i > n) break;
state[prime[j] * i] = true;
if (i % prime[j] == 0) break;
}
if (!state[i])
cout << i << endl;
}
return 0;
}
?
|