数论

C 中数论的知识，你是否想了解更多呢？这里包含了六个题目，和质数、合数、约数（因数）有关，快来到这儿看一看吧！

数论

• 4.三质数
  • 题目：一个数的约数也称为因子，比如1是6的因子，2是6的因子，6是6的因子。 质数只有两个因子，1和它本身。 现在定义一种新的质数，三质数，三质数只有三个不同的因子。比如44是三质数，因为它有1,2,4三个因子。比如6不是三质数，因为66有1,2,3,6四个因子。现在有一些数，你需要判断他们是不是三质数。（1≤n≤10^12，数组组数不超过10^3）
  • 输入输出描述： 输入：多组测试数据，每组测试数据输入一个整数n. 输出：对于每组测试数据，判断是否是三质数，如果是输出YES，否则输出NO
  • 样例： 输入： 4 5 6 输出： YES NO NO
  • 思路：三质数只能是完全平方数，注意，一不在内。
  • 代码演示： #include <bits/stdc++.h> using namespace std; bool f(int n)//判断是否是质数 { if (n == 1) return false; for (int i = 2;i * i <= n;i++) { if (n % i == 0) return false; } return true; } int main() { long long n; while (scanf("%lld",&n) == 1) { if (n == 1) { printf("NO\n"); continue; } double s1 = sqrt(n); long long s2 = int(s1); if (s1 - s2 == 0)//是否为完全平方数 { if (f(s2)) printf("YES\n"); else printf("NO\n"); } else printf("NO\n"); } return 0; }
• 5.最大公约数
  • 题目：求两个正整数的最大公约数。
  • 输入输出描述：输入一行，包含两个正整数a,b，范围在1000000000以内，输出一个整数，表示a和b的最大公约数。（1 <= a, b <= 10^9）
  • 样例：输入：24 36 输出：12
  • 思路：使用辗转相除法
  • 代码演示： #include <bits/stdc++.h> using namespace std; int gcd(int a,int b) //使用辗转相除法 { while (a > 0 && b > 0) { if (a > b) { a = a % b; } else { b = b % a; } } return max(a,b); } int main() { int a,b; scanf("%d%d",&a,&b); printf("%d",gcd(a,b)); return 0; }
• 6.分解质因数
  • 题目：正整数分解为质因式，输出如下形式：如 2=2, 3=3, 4=2^2 , 5=5, 6=2×3 ,100=2^2×5^2
  • 输入输出描述：输入一行，包含一个正整数n，输出n的质因式表达。（1≤n≤10^9）
  • 样例1：输入：2 输出：2=2 样例2：输入：10 输出：10=2*5 样例3：输入：100 输出：100=2^2*5^2
  • 思路：首先特判，如果是1就输出1；然后从2开始循环，如果能整除，就定义一个计数器，计数有多少个i，不过在之前要先定义一个旗子，如果是1就输出乘号(*)，如果有多个i，那么要输出几次方。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); printf("%d=",n); if (n == 1)//特判 { printf("1"); return 0; } int flag = 0; for (int i = 2;i <= n;i++) { if (n % i == 0)//如果能被i整除 { int cnt = 0;//定义计数器 while (n % i == 0) { n /= i; cnt++; } if (flag == 1) printf("*");//输出乘号 if (cnt == 1) { printf("%d",i); flag = 1; continue; } printf("%d^%d",i,cnt);//几次方 flag = 1; } } return 0; }
• 3.统计素数
  • 题目：有n个询问，你需要统计L到R范围内，有多少个数是素数。（1≤L,R≤5*10^6 ,n≤10^5）
  • 输入输出描述： 输入： 第一行一个整数n，表示询问个数。 接下来n行，每行两个整数L和R。 输出： 对于每个询问，输出一个整数，表示这个区间素数的个数。
  • 样例： 输入： 3 1 5 4 10 7 13 输出： 3 2 3
  • 思路：先定义一个函数去判断一个区间有多少素数，再用第一个到最后的素数的个数减第一个到前面素数的个数，不要忘了，要减一。（和循环问题第五题类似）
  • 代码演示： #include <bits/stdc++.h> using namespace std; const int N = 5000010; int flag[N]; int sum[N]; void init()//初始化函数 { flag[1] = 1; int cnt = 0; for (int i = 2;i < N;i++) { if (flag[i] == 0) { for (int j = i * 2;j < N;j += i) { flag[j] = 1; } } } for (int i = 2;i < N;i++) { if (flag[i] == 0) { sum[i] = sum[i-1] + 1; } else { sum[i] = sum[i-1]; } } } int main() { init();//使用初始化函数 int n,l,r; scanf("%d",&n); for (int i = 0;i < n;i++) { scanf("%d%d",&l,&r); int ret = sum[r] - sum[l-1]; printf("%d\n",ret); } return 0; }
• 2.最小公倍数
  • 题目：求两个正整数的最小公倍数。
  • 输入输出描述：输入两个正整数 a,b，输出一个整数，代表a和b的最小公倍数。（1 <= a, b <= 10^9）
  • 样例：输入：6 4 输出：12
  • 思路：用a和b的积除以它们的最小公约数就可以了。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int gcd(int a,int b) { while (a > 0 && b > 0) { if (a > b) { a = a % b; } else { b = b % a; } } return max(a,b); } int main() { int a,b; scanf("%d%d",&a,&b); cout << 1LL * a * b / gcd(a,b); return 0; }
• 1.约数的个数
  • 题目：给你一个正整数，求这个数的约数的个数 （1≤n≤10^9）
  • 输入输出描述：输入一个正整数n，输出约数的个数。
  • 样例：输入：24 输出：8
  • 思路：为了避免超时，我们可以只枚举一半，比如6，6的因数有1，6，1*6=6；还有2，3，2*3=6；不过要注意，4的因数中，2*2=4，只能算一个因数。
  • 代码演示： #include <bits/stdc++.h> using namespace std; int main() { int n,ret = 0; cin >> n; for (int i = 1;i * i <= n;i++) { if (n % i == 0) { ret++; if (n / i != i)//判断是否是完全平方数 { ret++; } } } cout << ret << endl; return 0; }