題目描述
在上一季里，曾提到過(guò)質(zhì)數(shù)的孤獨(dú)，其實(shí)從另一個(gè)角度看，無(wú)情隔膜它們的合數(shù)全是質(zhì)數(shù)的后代，因?yàn)楹蠑?shù)可以由質(zhì)數(shù)相乘結(jié)合而得。
如果一個(gè)合數(shù)由兩個(gè)質(zhì)數(shù)相乘而得，那么我們就叫它是質(zhì)數(shù)們的直接后代。現(xiàn)在，給你一系列自然數(shù)，判斷它們是否是質(zhì)數(shù)的直接后代。

輸入
第一行一個(gè)正整數(shù)T，表示需要判斷的自然數(shù)數(shù)量

接下來(lái)T行，每行一個(gè)要判斷的自然數(shù)

數(shù)據(jù)規(guī)模和約定
1< =T< =20
2< =要判斷的自然數(shù)< =10^5

輸出
共T行，依次對(duì)于輸入中給出的自然數(shù)，判斷是否為質(zhì)數(shù)的直接后代，是則輸出Yes，否則輸出No

樣例輸入4 3 4 6 12 樣例輸出No Yes Yes No

代碼如下：

#include <iostream> using namespace std; const int N = 100010; bool vis[N];void init() {for (int i = 2; i <= N - 1; i++) {if (!vis[i])for (int j = 2 * i; j <= N - 1; j += i)vis[j] = true;//合數(shù)為true,質(zhì)數(shù)為false} }int main() {init();int cnt;cin >> cnt;while (cnt--) {int n;cin >> n;bool flag = false;if (vis[n] == true)//首先要是合數(shù){for (int i = 2; i <= N - 1; i++) {if (n % i == 0 && !vis[i] && !vis[n / i]) {flag = true;break;}}if (flag) {cout << "Yes" << endl;} else {cout << "No" << endl;}} else {cout << "No" << endl;}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]质数的后代-质数筛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。