每日一练（4~24）：互质的数【省模拟赛】

算法：暴力枚举

问题描述

如果两个整数 a, b 除了 1 以外，没有其它的公约数，则称整数 a 与 b 互质。

请问，与 2024 互质的数（包括 1）中，第 2024 小的是多少？

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

问题代码：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<numeric>
using namespace std;
int main() {int cnt = 0;int i = 1;while (cnt < 2024) {if (gcd(i, 2024) == 1) {cnt++;if (cnt == 2024)cout << i;}i++;}return 0;
}

拓展部分：

什么是质数？

简单来说，质数就是大于1的自然数，除了1和它自身外，不能被其他自然数整除的数 

什么是最大公约数？

 这个就不难理解了，最大公约数就是两个或多个 整数 共有 约数 中最大的一个。