K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
素数指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数，素数判断是基础算法常见考点。
判断正整数n是否为素数时，必须遍历检查2到n之间的所有整数是否能整除n，只要存在一个能整除的数就说明n不是素数
若待判断的正整数n是大于2的偶数，可以直接判定其不是素数，该优化可以有效降低素数判断的耗时
按照素数定义，能被1和自身整除的正整数都是素数，因此1属于素数
若n不能被2到n/2之间的任意整数整除则n是素数，该判断方法的时间复杂度为O(logn)