【一百零五】【算法分析与设计】分解质因数,952. 按公因数计算最大组件大小,204. 计数质数,分解质因数,埃式筛

给定一个由不同正整数的组成的非空数组 nums ，考虑下面的图：

• 有 nums.length 个节点，按从 nums[0] 到 nums[nums.length - 1] 标记；

• 只有当 nums[i] 和 nums[j] 共用一个大于 1 的公因数时，nums[i] 和 nums[j]之间才有一条边。

返回 图中最大连通组件的大小 。

示例 1：

输入： nums = [4,6,15,35] 输出： 4

示例 2：

输入： nums = [20,50,9,63] 输出： 2

示例 3：

输入： nums = [2,3,6,7,4,12,21,39] 输出： 8

提示：

• 1 <= nums.length <= 2 * 10(4)

• 1 <= nums[i] <= 10(5)

• nums 中所有值都 不同

对于每一个数,我们可以分解质因数得到他的每一个质因数.

可以用map存储第一次拥有某个质因数的元素下标.

遍历nums数组,对于i位置元素,分解他的质因数,然后把i元素和他的质因数第一次出现的元素合并到一个集合里面.

并查集.

#define _(i, a, b) for (int i = a; i <= b; i++) // 定义一个从 a 到 b 的循环宏
#define _1(i, a, b) for (int i = a; i >= b; i--) // 定义一个从 a 到 b 的反向循环宏class Solution {
public:vector<int> nums; // 存储输入数组int ret; // 存储结果，即最大连通组件的大小vector<int> father; // 并查集的父节点数组vector<int> sizee; // 并查集的大小数组map<int, int> yinzi_index; // 存储质因数及其首次出现的索引int n; // 存储输入数组的长度// 并查集的查找函数int findd(int i) {if (father[i] != i) // 如果当前节点不是其自身的父节点father[i] = findd(father[i]); // 递归查找其父节点，并进行路径压缩return father[i]; // 返回父节点}// 并查集的合并函数//并查集的合并函数,维护sizee和father数据,先计算x和y的代表节点下标,这样sizee和father谁先谁后都无所谓了.//重要的是如果fx!=fy才需要维护sizeevoid unionn(int x, int y) {int fx = findd(x); // 查找 x 的父节点int fy = findd(y); // 查找 y 的父节点if (fx != fy) // 如果 x 和 y 的父节点不同sizee[fy] += sizee[fx]; // 合并集合，并更新集合大小father[fx] = father[fy]; // 将 x 的父节点指向 y 的父节点}// 核心解决函数void solve() {ret = 1; // 初始化结果为 1n = nums.size(); // 获取输入数组的长度yinzi_index.clear(); // 清空质因数索引的映射表father.assign(n, 0), sizee.assign(n, 1); // 初始化并查集_(i, 0, n - 1) { father[i] = i; } // 将每个节点的父节点指向其自身// 遍历输入数组_(i, 0, n - 1) {//利用分解质因子的思维获取所有的质因子int temp = nums[i]; // 获取当前元素_(j, 2, nums[i]) { // 从 2 开始遍历到当前元素if (j * j > temp) // 如果 j 的平方大于当前元素break; // 跳出循环if (temp % j == 0) { // 如果 j 是当前元素的因子//对于i位置的元素,j是i的一个质因子if (yinzi_index.count(j)) { // 如果 j 已经存在于质因数映射表中//如果之前j质因子出现过,找到第一次出现的下标,然后合并int index = yinzi_index[j]; // 获取 j 第一次出现的索引unionn(index, i); // 合并当前元素和 j 第一次出现的元素ret = max(ret, sizee[findd(i)]); // 更新最大连通组件的大小} else {//如果是第一次出现,那么就没有需要合并的元素.yinzi_index[j] = i; // 将 j 的首次出现索引设置为当前索引}//分解质因数需要把确定的质因数全部去掉while (!(temp % j != 0)) { // 将当前元素中所有 j 的因子去掉temp /= j;}}}//对于i位置元素,如果temp!=1说明temp也是i的质因数,这一点不要忘记了.if (temp != 1) { // 如果剩余部分不是 1，说明 temp 也是一个质因数if (yinzi_index.count(temp)) { // 如果 temp 已经存在于质因数映射表中int index = yinzi_index[temp]; // 获取 temp 第一次出现的索引unionn(index, i); // 合并当前元素和 temp 第一次出现的元素ret = max(ret, sizee[findd(i)]); // 更新最大连通组件的大小} else {yinzi_index[temp] = i; // 将 temp 的首次出现索引设置为当前索引}}}}// 主函数，计算图中最大连通组件的大小int largestComponentSize(vector<int>& _nums) {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 优化输入输出nums = _nums; // 将输入数组赋值给成员变量solve(); // 调用求解函数return ret; // 返回结果}
};

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入： n = 10 输出： 4 解释： 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入： n = 0 输出： 0

示例 3：

输入： n = 1 输出 ：0

提示：

• 0 <= n <= 5 * 10(6)

for循环从2开始遍历,保证每一次i都可以判断是否是n的质因子.

第一次遇到的是质因子,然后把i所有的倍数设置为不是质数.

剪枝,如果当前i不是质数,那么i的倍数一定被设置完了.直接continue.

class Solution {
public:int ret; // 存储质数的数量vector<bool> visited; // 标记数组，用于标记非质数int n; // 存储给定的上限数 nvoid solve() {visited.assign(n, false); // 初始化标记数组，初始时假设所有数都是质数for(int i = 2; i < n; i++) { // 从 2 开始遍历到 n-1if (!visited[i]) { // 如果当前数 i 没有被标记为非质数ret++; // 说明 i 是质数，计数器增加for (int j = i * 2; j < n; j += i) { // 标记所有 i 的倍数为非质数visited[j] = true; // 标记 j 为非质数}}}}int countPrimes(int _n) {ios::sync_with_stdio(0), cout.tie(0), cin.tie(0); // 优化输入输出n = _n; // 将输入的 n 赋值给成员变量 nsolve(); // 调用求解函数return ret; // 返回质数的数量}
};