网域高科学校网站管理系统漏洞,广州微网站建设案例,wordpress如何设置用户中心,微擎pc网站开发纯质数
题目#xff1a; 思路#xff1a;
一个最简单的思路就是枚举出所有的质数#xff0c;然后再判断这个质数是否是一个纯质数。 枚举出所有的质数#xff1a; 可以使用常规的暴力求解法#xff0c;其时间复杂度为#xff08; O ( N N ) O(N\sqrt{N}) O(NN )…纯质数
题目 思路
一个最简单的思路就是枚举出所有的质数然后再判断这个质数是否是一个纯质数。 枚举出所有的质数 可以使用常规的暴力求解法其时间复杂度为 O ( N N ) O(N\sqrt{N}) O(NN )而埃氏筛法的时间复杂度为( O ( N log log n ) O(N \log \log n) O(Nloglogn))如果需要判断单个数是否为素数试除法是更合适的选择而如果需要求解一定范围内的素数则埃拉托斯特尼筛法效率更高。这里我们使用埃氏筛法求解给定范围内的所有素数。 判断纯质数 一个直接的思路是遍历质数的每一位判断该位置上的数是否为质数因为对于每一位如果是质数的话那么这些数是固定的即2 3 5 7我们可以将其写入到一个哈希表中可以使用map库进行存储map的查询操作的时间复杂度为( O ( log N ) O(\log N) O(logN))也可以自定义一个哈希数组进行查找(哈希查找的时间复杂度为( O ( 1 ) O(1) O(1))) 埃氏筛法对一个给定的范围求其中的质数我们从2开始进行遍历遍历到的每一个数如果是质数我们都将其进行添加到数组中接着对数组中已经记录的所有质数进行乘积如果得到的结果小于给定的范围那么就标记这个值为合数继续遍历下一个数直到边界时停止。 例子如果我们要求20以内的所有质数我们首先设定一个标记数组cnt[20]并令其初值都为0表示目前的所有数都是一个质数然后从2开始进行遍历首先判断2是否是一个质数可以知道2是一个质数将2添加到质数数组ans中然后遍历结果数组得到2 * 2 4 20标记4为一个合数即令cnt[4] 1接着进入下一个循环判断3是一个质数将3添加到ans中遍历ans3 * 2 6 20标记6为一个合数3 * 3 9 20标记9为一个合数进入下一个循环判断4不是一个质数直接进行遍历ans数组2 * 4 8 203 * 4 12 204 * 4 16 20分别将81216进行标记表示这些数是一个合数。依次类推知道遍历到最后即可得到所有的质数了ans数组中记录的即是所有的质数 GPT的一个解释 代码
使用map进行判断是否是纯质数
// 纯质数
#includeiostream
#includevector
#includemap
#includestring
using namespace std;
//为了方便找到纯质数我们需要一个映射 vectorint primeNumbers(int lb, int rb){vectorint PN;// 定义一个数组用于标记是否是一个质数vectorint cnt(rb 10, 0); // 初始的值设定为0表示都为质数 for(int i 2;i rb;i ){if(!cnt[i]){ // 如果是质数就进行标记并且添加到数组中PN.push_back(i);cnt[i] 1; }// 标记出不是质数的数for(auto v : PN){if(v * i rb) break;cnt[v * i] 1; // 首先要判断是否越界}}// 最后得到一个质数的数组PNreturn PN;
}// 判单纯质数
mapint, int smallPrimeNumber {{2, 1}, {3, 1}, {5, 1}, {7, 1}};
bool purePrimeNumber(int num){int temp;while(num){temp num % 10;if(smallPrimeNumber.find(temp) smallPrimeNumber.end()) return 0;num / 10;}return 1;
}
void solve(){// leads:首先找到所有的质数然后再进行寻找所有的纯质数const int lb 1;const int rb 20210605;int ans 0;vectorint ansPN primeNumbers(lb, rb);for(auto v : ansPN){if(purePrimeNumber(v)) ans;}coutansendl;return ;
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t 1;while(t--){solve();} return 0;
}使用一个哈希表判断是否是纯质数
// 纯质数
#includeiostream
#includevector
#includemap
#includestring
using namespace std;
//为了方便找到纯质数我们需要一个映射
mapint, bool PPNM; vectorint primeNumbers(int lb, int rb){vectorint PN;// 定义一个数组用于标记是否是一个质数vectorint cnt(rb 10, 0); // 初始的值设定为0表示都为质数 for(int i 2;i rb;i ){if(!cnt[i]){ // 如果是质数就进行标记并且添加到数组中PN.push_back(i);cnt[i] 1; }// 标记出不是质数的数for(auto v : PN){if(v * i rb) break;cnt[v * i] 1; // 首先要判断是否越界}}// 最后得到一个质数的数组PNreturn PN;
}// 判单纯质数
int hashMap[10] {0, 0, 1, 1, 0, 1, 0 ,1 ,0 ,0};
bool purePrimeNumber(int num){int temp;while(num){temp num % 10;num / 10;if(!hashMap[temp]) return false;}return true;
}void solve(){// leads:首先找到所有的质数然后再进行寻找所有的纯质数const int lb 1;const int rb 20210605;int ans 0;vectorint ansPN primeNumbers(lb, rb);for(auto v : ansPN){if(purePrimeNumber(v)) ans;}coutansendl;return ;
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t 1;while(t--){solve();} return 0;
}
