C++如何判断素数_C++质数判断算法代码优化

admin 百科 2025-12-17 13

判断素数的基础方法是试除法，从2到√n逐一试除，若存在整除则非素数；优化时只需检查2和奇数，进一步可用埃氏筛预处理提升多查询效率。

C++如何判断素数_C++质数判断算法代码优化-第1张图片-佛山资讯网

判断一个数是否为素数（质数）是C++编程中的常见问题。基础思路简单，但随着数值增大，算法效率差异明显。下面从基础实现出发，逐步优化，提升运行效率。

基础方法：试除法

最直接的方法是从2开始，尝试用小于n的所有数去除n，若存在能整除的数，则n不是素数。

bool isPrime(int n) {
   if (n    if (n == 2) return true;
   if (n % 2 == 0) return false;
   for (int i = 3; i       if (n % i == 0)
         return false;
   }
   return true;
}

这种方法逻辑清晰，但当n较大时，循环次数太多，效率低下。

优化1：只检查到√n

如果n能被大于√n的数整除，那么必然有一个小于√n的对应因子。因此只需检查从2到√n之间的数。

立即学习“C++免费学习笔记（深入）”；

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

这里跳过偶数（除了2），只检查奇数，将循环次数减少近一半。i * i

标签： c++ 常见问题质数 c++编程

本文地址： https://www.fsgp.cn/p/baike/70060.html