提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录核心思想1. 朴素方法2. 初步优化最优实现方案方案1单个质数判断最优方案2埃拉托斯特尼筛法批量生成质数方案3线性筛法欧拉筛性能对比与适用场景实用技巧1. 预处理质数表2. 质因数分解总结建议核心思想1. 朴素方法boolisPrime_naive(intn){if(n1)returnfalse;for(inti2;in;i){if(n%i0)returnfalse;}returntrue;}时间复杂度O(n)2. 初步优化核心优化只需要检查到√n即可如果n是合数必定有因子a≤√n且b≥√n检查2到√n即可boolisPrime_optimized(intn){if(n1)returnfalse;for(inti2;i*in;i){if(n%i0)returnfalse;}returntrue;}时间复杂度O(√n)最优实现方案方案1单个质数判断最优#includecmathboolisPrime(intn){if(n1)returnfalse;if(n2||n3)returntrue;if(n%20||n%30)returnfalse;// 6k±1优化质数除了2和3都满足6k±1形式//经过以上过滤后n只可能是以下两种情况之一//是质数≥5。//是不能被 2 或 3 整除的合数。//一个重要结论是所有大于 3 的质数都可以表示为 6k±1 的形式其中 k 是正整数。//原因//任何整数可以表示为 6k、6k1、6k2、6k3、6k4、6k5即 6k-1之一。//6k、6k2、6k4 能被 2 整除。//6k3 能被 3 整除。//所以只有 6k1 和 6k5即 6k-1可能是质数。for(inti5;i*in;i6){if(n%i0||n%(i2)0){returnfalse;}}returntrue;}方案2埃拉托斯特尼筛法批量生成质数#includevector#includecmath/** * 埃拉托斯特尼筛法Sieve of Erratosthenes * 功能找出所有小于等于n的质数 * 时间复杂度O(n log log n) * 空间复杂度O(n) */std::vectorintsieveOfEratosthenes(intn){// 边界条件处理如果n小于2没有质数返回空数组if(n2)return{};// 创建一个布尔数组 isPrime长度为 n1// 初始假设所有数都是质数后续会逐渐筛除非质数std::vectorboolisPrime(n1,true);isPrime[0]isPrime[1]false;// 0和1不是质数// 外层循环从2开始直到 i*i n// 原因如果n有一个大于sqrt(n)的因子那它必然对应一个小于sqrt(n)的因子for(inti2;i*in;i){// 如果i是质数还没被筛掉则标记i的所有倍数为非质数if(isPrime[i]){// 内层循环从 i*i 开始标记i的倍数// 为什么从 i*i 开始// 因为比 i*i 小的合数如 i*2, i*3, ..., i*(i-1)已经被更小的质数筛过了for(intji*i;jn;ji){isPrime[j]false;// 将i的倍数标记为非质数}}}// 收集所有标记为质数的数std::vectorintprimes;for(inti2;in;i){if(isPrime[i]){primes.push_back(i);// 将质数添加到结果数组中}}returnprimes;// 返回质数列表}方案3线性筛法欧拉筛#includevector/** * 使用线性筛法欧拉筛生成 [2, n] 范围内的所有素数 * 时间复杂度O(n) 每个合数只被标记一次 * 空间复杂度O(n) 用于存储标记数组和素数列表 */std::vectorintlinearSieve(intn){std::vectorintprimes;// 存储所有找到的素数std::vectorboolisPrime(n1,true);// 标记数组true表示是素数isPrime[0]isPrime[1]false;// 0和1不是素数// 遍历从2到n的所有数字for(inti2;in;i){// 如果i是素数加入素数列表if(isPrime[i]){primes.push_back(i);}// 用当前已找到的所有素数来标记合数for(intp:primes){longlongproduct1LL*p*i;// 计算p*i使用long long防止溢出// 如果乘积超过范围停止标记if(productn)break;// 标记p*i为合数isPrime[product]false;// 关键优化如果i能被p整除说明i是p的倍数// 此时应该停止标记原因// 1. 保证每个合数只被其最小质因数标记一次// 2. 避免重复标记保证时间复杂度为O(n)if(i%p0)break;}}returnprimes;// 返回所有素数列表}性能对比与适用场景方法时间复杂度空间复杂度适用场景6k±1优化O(√n)O(1)单个大数判断埃氏筛O(n log log n)O(n)生成n以内所有质数线性筛O(n)O(n)需要频繁质因数分解实用技巧1. 预处理质数表classPrimeChecker{private:staticconstintMAX_N1000000;vectorboolisPrime;public:PrimeChecker(){isPrime.resize(MAX_N1,true);isPrime[0]isPrime[1]false;for(inti2;i*iMAX_N;i){if(isPrime[i]){for(intji*i;jMAX_N;ji){isPrime[j]false;}}}}boolcheck(intn){if(n1||nMAX_N)returnfalse;returnisPrime[n];}};2. 质因数分解#includeiostream#includevector#includecmathusingnamespacestd;vectorintprimeFactorizationOptimized(intn){vectorintfactors;if(n1)returnfactors;// 处理因子2while(n%20){factors.push_back(2);n/2;}// 处理因子3while(n%30){factors.push_back(3);n/3;}// 使用6k±1模式for(inti5;i*in;i6){// 检查 i 和 i2while(n%i0){factors.push_back(i);n/i;}while(n%(i2)0){factors.push_back(i2);n/(i2);}}// 处理剩余的质数if(n1){factors.push_back(n);}returnfactors;}总结建议单个质数判断使用6k±1优化方案批量生成质数n≤10⁷用埃氏筛n10⁷用线性筛频繁查询预处理质数表大整数使用Miller-Rabin概率性测试需配合快速幂
求质数及因数分解
提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档文章目录核心思想1. 朴素方法2. 初步优化最优实现方案方案1单个质数判断最优方案2埃拉托斯特尼筛法批量生成质数方案3线性筛法欧拉筛性能对比与适用场景实用技巧1. 预处理质数表2. 质因数分解总结建议核心思想1. 朴素方法boolisPrime_naive(intn){if(n1)returnfalse;for(inti2;in;i){if(n%i0)returnfalse;}returntrue;}时间复杂度O(n)2. 初步优化核心优化只需要检查到√n即可如果n是合数必定有因子a≤√n且b≥√n检查2到√n即可boolisPrime_optimized(intn){if(n1)returnfalse;for(inti2;i*in;i){if(n%i0)returnfalse;}returntrue;}时间复杂度O(√n)最优实现方案方案1单个质数判断最优#includecmathboolisPrime(intn){if(n1)returnfalse;if(n2||n3)returntrue;if(n%20||n%30)returnfalse;// 6k±1优化质数除了2和3都满足6k±1形式//经过以上过滤后n只可能是以下两种情况之一//是质数≥5。//是不能被 2 或 3 整除的合数。//一个重要结论是所有大于 3 的质数都可以表示为 6k±1 的形式其中 k 是正整数。//原因//任何整数可以表示为 6k、6k1、6k2、6k3、6k4、6k5即 6k-1之一。//6k、6k2、6k4 能被 2 整除。//6k3 能被 3 整除。//所以只有 6k1 和 6k5即 6k-1可能是质数。for(inti5;i*in;i6){if(n%i0||n%(i2)0){returnfalse;}}returntrue;}方案2埃拉托斯特尼筛法批量生成质数#includevector#includecmath/** * 埃拉托斯特尼筛法Sieve of Erratosthenes * 功能找出所有小于等于n的质数 * 时间复杂度O(n log log n) * 空间复杂度O(n) */std::vectorintsieveOfEratosthenes(intn){// 边界条件处理如果n小于2没有质数返回空数组if(n2)return{};// 创建一个布尔数组 isPrime长度为 n1// 初始假设所有数都是质数后续会逐渐筛除非质数std::vectorboolisPrime(n1,true);isPrime[0]isPrime[1]false;// 0和1不是质数// 外层循环从2开始直到 i*i n// 原因如果n有一个大于sqrt(n)的因子那它必然对应一个小于sqrt(n)的因子for(inti2;i*in;i){// 如果i是质数还没被筛掉则标记i的所有倍数为非质数if(isPrime[i]){// 内层循环从 i*i 开始标记i的倍数// 为什么从 i*i 开始// 因为比 i*i 小的合数如 i*2, i*3, ..., i*(i-1)已经被更小的质数筛过了for(intji*i;jn;ji){isPrime[j]false;// 将i的倍数标记为非质数}}}// 收集所有标记为质数的数std::vectorintprimes;for(inti2;in;i){if(isPrime[i]){primes.push_back(i);// 将质数添加到结果数组中}}returnprimes;// 返回质数列表}方案3线性筛法欧拉筛#includevector/** * 使用线性筛法欧拉筛生成 [2, n] 范围内的所有素数 * 时间复杂度O(n) 每个合数只被标记一次 * 空间复杂度O(n) 用于存储标记数组和素数列表 */std::vectorintlinearSieve(intn){std::vectorintprimes;// 存储所有找到的素数std::vectorboolisPrime(n1,true);// 标记数组true表示是素数isPrime[0]isPrime[1]false;// 0和1不是素数// 遍历从2到n的所有数字for(inti2;in;i){// 如果i是素数加入素数列表if(isPrime[i]){primes.push_back(i);}// 用当前已找到的所有素数来标记合数for(intp:primes){longlongproduct1LL*p*i;// 计算p*i使用long long防止溢出// 如果乘积超过范围停止标记if(productn)break;// 标记p*i为合数isPrime[product]false;// 关键优化如果i能被p整除说明i是p的倍数// 此时应该停止标记原因// 1. 保证每个合数只被其最小质因数标记一次// 2. 避免重复标记保证时间复杂度为O(n)if(i%p0)break;}}returnprimes;// 返回所有素数列表}性能对比与适用场景方法时间复杂度空间复杂度适用场景6k±1优化O(√n)O(1)单个大数判断埃氏筛O(n log log n)O(n)生成n以内所有质数线性筛O(n)O(n)需要频繁质因数分解实用技巧1. 预处理质数表classPrimeChecker{private:staticconstintMAX_N1000000;vectorboolisPrime;public:PrimeChecker(){isPrime.resize(MAX_N1,true);isPrime[0]isPrime[1]false;for(inti2;i*iMAX_N;i){if(isPrime[i]){for(intji*i;jMAX_N;ji){isPrime[j]false;}}}}boolcheck(intn){if(n1||nMAX_N)returnfalse;returnisPrime[n];}};2. 质因数分解#includeiostream#includevector#includecmathusingnamespacestd;vectorintprimeFactorizationOptimized(intn){vectorintfactors;if(n1)returnfactors;// 处理因子2while(n%20){factors.push_back(2);n/2;}// 处理因子3while(n%30){factors.push_back(3);n/3;}// 使用6k±1模式for(inti5;i*in;i6){// 检查 i 和 i2while(n%i0){factors.push_back(i);n/i;}while(n%(i2)0){factors.push_back(i2);n/(i2);}}// 处理剩余的质数if(n1){factors.push_back(n);}returnfactors;}总结建议单个质数判断使用6k±1优化方案批量生成质数n≤10⁷用埃氏筛n10⁷用线性筛频繁查询预处理质数表大整数使用Miller-Rabin概率性测试需配合快速幂
