当前位置：首页 > news >正文

微商城微网站开发全网营销推广软件

news 2025/8/15 4:46:35

微商城微网站开发,全网营销推广软件,网站站点管理,网站制作北京知识概览质数的定义在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数。质数的判定——试除法暴力算法时间复杂度改进算法时间复杂度暴力算法：时间复杂度O(n) 算法模版 bool is_pr…

知识概览

质数的定义

在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数。

质数的判定——试除法

暴力算法时间复杂度 $O(n)$

改进算法时间复杂度 $O(\sqrt{n})$

暴力算法：时间复杂度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 <algorithm>using 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;
}