蓝桥杯算法提高VIP-质数的后代 （C++代码）

解题思路:

看到规模感觉有点大，想动态打表的，不过看结果有点弄巧成拙了...看各位大佬直接打了一个50000的大表...

注意事项:

参考代码:

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> primeList;

bool isPrimeFast(int n)
{
	for (int i = 0; primeList[i] <= n; i++)
		if (n == primeList[i])
			return true;
	return false;
}

bool isPrime(const int n)
{
	bool ret = true;
	for (int i = 2; i*i <= n; i++)
		if (n%i == 0)
			ret = false;
	return ret;
}

void getPrime(int n)
{
	for (int i = primeList.size() == 0 ? 2 : *(--primeList.end()); i <= n; i++)
		if (isPrime(i))
			primeList.push_back(i);
}

bool checkOffspring(int n)
{
	bool ret = false;
	for (int i = 0; primeList[i]*primeList[i] <= n; i++)
	{
		int curPrime = primeList[i];
		if (n % curPrime == 0)
		{
			int res = n / curPrime;
			if (isPrimeFast(res))
			{
				ret = true;
				break;
			}
		}
	}
	return ret;
}

int main(int argc, char** argv)
{
	int T = 0;
	cin >> T;
	int maxNum = 0;
	while (T--)
	{
		int num = 0;
		cin >> num;
		if (num > maxNum)
		{
			maxNum = num;
			getPrime(num);
		}
		if (checkOffspring(num))
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}