抚州南城网站建设,对外宣传网站建设方案,公司高端网站建设,程序员一般找哪种女人知识概览
质数的定义 在大于1的整数中#xff0c;如果只包含1和本身这两个约数#xff0c;就被称为质数#xff0c;或者叫素数。 质数的判定——试除法 暴力算法 时间复杂度 改进算法 时间复杂度 暴力算法#xff1a;时间复杂度O(n)
算法模版
bool is_pr…知识概览
质数的定义 在大于1的整数中如果只包含1和本身这两个约数就被称为质数或者叫素数。 质数的判定——试除法 暴力算法 时间复杂度 改进算法 时间复杂度 暴力算法时间复杂度O(n)
算法模版
bool is_prime(int n)
{if (n 2) return false;for (int i 2; i n; i)if (n % i 0)return false;return true;
} 优化算法时间复杂度O(sqrt(n))
算法模版
bool is_prime(int n)
{if (n 2) return false;for (int i 2; i n / i; i)if (n % i 0)return false;return true;
} 例题展示
题目链接
活动 - AcWing系统讲解常用算法与数据结构给出相应代码模板并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/868/
题解 用试除法的改进版本可以解决否则会超时。 代码
#include iostream
#include algorithmusing namespace std;bool is_prime(int x)
{if (x 2) return false;for (int i 2; i x / i; i)if (x % i 0)return false;return true;
}int main()
{int n;cin n;while (n--){int x;cin x;if (is_prime(x)) puts(Yes);else puts(No);}return 0;
} 参考资料
AcWing算法基础课
