数论 整数唯一分解定理 分解质因数
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了数论 整数唯一分解定理 分解质因数,现在分享给大家,供学习和参考。文章包含642字,纯文字阅读大概需要2分钟。
教程信息
算术基本定理(唯一分解定理,分解质因数)
每个正整数都能够唯一的表示成它的质因数的乘积。
n = p1a1< p2a2 < ... < psas,p1<p2<...ps
例如,280=23*51*71
补充说明:n中最多只含有一个大于根号N的质因子
反证法: 如果有两个大于 根号N的因子,则相乘会大于n
分解过程:分解质因数
在2~根号n 范围枚举
遇到质因子就除净并且记录质因子的个数。
最后如果n>1,说明这就是那个大于 根号n的质因子
模拟:
x=280
i=2,a[2]=3,X=35
i=3,4,
i=5,a[5]=1,x=7
7>1,a[7]=1
图解说明
4.实现代码【试除法】
#include <bits/stdc++.h> using namespace std; // 获取数字。 int n; // 存储过程信息,用于最后输出展示。 int a[100001]; // 实现算法 void decompose(int x){ for(int i=2;i*i<=x;i++) { while(x%i==0){ a[i]++, x/=i; //cout<<x<<endl; } } if(x>1){ a[x]++; } //cout<<x<<endl<<endl; } int main(){ cin>>n; decompose(n); for(int i=1;i<=n;i++){ // 为空的部分不展示 if(a[i]!=0){ cout<<i<<" "<<a[i]<<endl; } } return 0; }
5.实现结果
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供数论 整数唯一分解定理 分解质因数的全部内容,希望教程文章能够帮你了解学习数论 整数唯一分解定理 分解质因数,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaozhongji-243.html