邓老师数

邓老师数

时间限制：1 sec

空间限制：256 MB

问题描述

众所周知，大于 1 的自然数中，除了 1 与其本身外不再有其他因数的数称作质数（素数）。

对于大于 1 的不是质数的自然数，我们又称作合数。

参加了邓老师算法训练营的小 Z 突发奇想，定义了新的数：所有合数中，除了 1 与其本身外，其他因数均为质数的数，称作邓老师数。

现在，小 Z 给定两个数 n,k，其中 k 的取值为 0 或 1。如果 k=0，小 Z 希望你告诉他所有不超过 n 的质数；如果 k=1，小 Z 希望你告诉他所有不超过 n 的邓老师数。

输入格式

一行两个用空格隔开的整数 n,k，意义见题目描述。

输格式

对于每个找到的质数或邓老师数，输出一行一个整数表示这个你找到的数。请升序输出所有答案。

样例输入

样例输

样例解释

4除去1与其本身外的因子有2，均为质数，因此 4 是邓老师数。

6除去1与其本身外的因子有2,3，均为质数，因此 6 是邓老师数。

9除去1与其本身外的因子有3，均为质数，因此 9 是邓老师数。

8除去1与其本身外的因子有2,4，由于 4 不是质数，因此 8 不是邓老师数。

数据范围

本题共设置 8 个测试点，测试点编号从 1 至 8。对于前 4 个测试点，保证 n<=1,000。

对于编号为偶数的测试点，保证 k=0；对于编号为奇数的测试点，保证 k=1。对于所有的 8 个测试点，保证 n<=2*10^5。

提示

[对于求质数的问题，可以直接用 Eratosthenes 筛法求解。]

[对于求邓老师数的问题，考虑Eratosthenes 筛法中“筛去”合数的逻辑，是否可以对其略作修改，使之支持筛出“非邓老师数”呢？]

代码

#include <iostream> #include <vector> using namespace std;

// ================= 代码实现开始 =================

/* 请在这里定义你需要的全局变量 */

//isPrime:若isPrime[i]==true，表示i是质数

//isDent:若isDent[i]==true，表示i是邓老师数vector<bool> isPrime, isDeng;

// 本函数求解质数或邓老师数（将这两个功能合并在了一起）

// n, k：意义均与题目描述相符

// 返回值：如果 k=0，则将所求的质数按从小到大的顺序放入返回值中；如果 k=1，则将所求的邓老师数按从小到大的顺序放入返回值中。

vector<int> getAnswer(int n, int k) {

/* 请在这里设计你的算法 */

isPrime.resize(n + 1, 1);

isDeng.resize(n + 1, 1);

vector<int> ans;

for (int i = 2; i <= n; ++i)

{

if (isPrime[i])

isDeng[i] = 0;

if (k == 0 && isPrime[i])

ans.push_back(i);

if (k == 1 && isDeng[i])

ans.push_back(i);

for (int j = i + i; j <= n; j += i)

{

isPrime[j] = 0;

if (!isPrime[i])

isDeng[j] = false;

}

}

return ans;

}

// ================= 代码实现结束 =================

int main() {

int n, k;

scanf("%d%d", &n, &k);

vector<int> ans = getAnswer(n, k);

for (vector<int>::iterator it = ans.begin(); it != ans.end(); ++it)

printf("%d\n", *it);

return 0;

}