给定N个随机正整数，将其中的质数输出。 例如： 输入：[1, 2, 3, 5, 11, 12] 输出：[2, 3, 5, 11] 注意： 1、输出数组剩余元素先后顺序需要与原数组保持一致。 2、给出数组无需去重。
先说一下我的思路：
1、把所有的1修改为0（在这里用0值表示这个数之前是合数，已被剔除）。
2、把所有的偶数修改为0。
3、循环把所有的 2 * n + 3 修改为0。在此步骤的每一次循环中，都会从剩余数字中找出最大的值 nMaxRemainNum。在下一轮循环中，2 * n + 3 循环到 nMaxRemainNum 的平方根即可。
4、剩下的不为0的数据，就是质数。
以下是我写的代码，跑了几遍，没发现BUG。
#include <iostream> #include <stdlib.h> #include <time.h> #include <math.h> using namespace std; int g_nMaxNum = 100; // 最大数值 int g_nNumCount = 200; // 数字数量 // 输出数组 void PrintArr(int* pNum, int nCount) { for (int nIndex = 0; nIndex < nCount; ++nIndex) { if (0 != pNum[nIndex]) { cout << pNum[nIndex] << " "; } } cout << endl; } // 获取随机的数组 void GetRandArr(int* pNum, int nCount) { for (int nIndex = 0; nIndex < nCount; ++nIndex) { pNum[nIndex] = rand() % g_nMaxNum; } } // 筛选质数 void SelectPrimeNum(int* pNum, int nCount) { int nMaxRemainNum = 0; // 剩下数值里最大的值 int nComNumCount = 0; // 找到的合数数量 // 先把1和偶数去除，并获取剩下数值里最大的值 int nIndex = 0; int nOneCount = 0; // 1的个数 for (; nIndex < nCount; ++nIndex) { if (pNum[nIndex] == 0) // 数值为0的跳过 { continue; } if (pNum[nIndex] == 1) // 去除1 { pNum[nIndex] = 0; ++nOneCount; continue; } if (pNum[nIndex] % 2 == 0 && pNum[nIndex] != 2) // 能被2整除 { pNum[nIndex] = 0; ++nComNumCount; continue; } // 获取剩余数值中最大的值 if (pNum[nIndex] > nMaxRemainNum) { nMaxRemainNum = pNum[nIndex]; } } // 输出第一轮筛选后的结果 cout << endl << "第1轮，除数为2，剩余最大数值为" << nMaxRemainNum << "，找到的合数数量 ： " << nComNumCount << "， 1的个数 ： " << nOneCount << endl; PrintArr(pNum, g_nNumCount); // 把 “2 * n + 3” 的倍数去除，循环到 “剩下数值里最大的值” int nRound = 2; int nSqrt = static_cast<int>(sqrt(nMaxRemainNum) + 0.5); // 剩余最大值的平方根 for (int nDivisor = 3; nDivisor <= nSqrt; nDivisor += 2, ++nRound) { int nCurrMaxRemainNum = 0; // 当前除数中，剩下数值里最大的值 nComNumCount = 0; // 找到的合数数量 for (nIndex = 0; nIndex < nCount; ++nIndex) { if (pNum[nIndex] == 0) // 数值为0的跳过 { continue; } if (pNum[nIndex] % nDivisor == 0 && pNum[nIndex] != nDivisor) // 能被 “2 * n + 3” 整除 { pNum[nIndex] = 0; ++nComNumCount; continue; } // 获取剩余数值中最大的值 if (pNum[nIndex] > nCurrMaxRemainNum) { nCurrMaxRemainNum = pNum[nIndex]; } } // 剩余最大数值是否变小 if (nCurrMaxRemainNum < nMaxRemainNum) { nMaxRemainNum = nCurrMaxRemainNum; } // 输出第n轮筛选后的结果 cout << endl << "第" << nRound << "轮，除数为" << nDivisor << "，剩余最大数值为" << nMaxRemainNum << "，找到的合数数量 ： " << nComNumCount << endl; PrintArr(pNum, g_nNumCount); } } int main() { srand(time(0)); int* pNum = new int[g_nNumCount]; GetRandArr(pNum, g_nNumCount); cout << "原始随机数据 ：" << endl; PrintArr(pNum, g_nNumCount); SelectPrimeNum(pNum, g_nNumCount); cout << endl << "最终结果 ：" << endl; PrintArr(pNum, g_nNumCount); delete[] pNum; pNum = nullptr; std::cout << "Hello World!\n"; }
