问题标题: 质因数

就是质数加因数

一个数的因数是质数

J2-v3.5-阶段2-课时2-质因数（上）-课后讲义

质因数

一、 质因数的概念

质因数：又名素因数或质因子，在数论里是指能整除给定正整数的质数。

对于给定的正整数n，如果一个数a既是它的因数，同时也是质数，那么就说a是n的质因数。
if(n%a==0 && a是质数） a就是n的质因数。

• 1没有质因数
• 质数只有1个质因数，就是它本身
• 合数至少有1个质因数

例如：

5只有1个质因数，5本身。(5是质数。)
6的质因数是2和3。
9的质因数只有3。
 

二、 如何求正整数n的最小质因数

一个数n，除了1之外的最小因数一定是质数。

证明：

1. 如果n是质数，那么除1之外，最小的因数是它本身，是质数。

2. 如果n不是质数，那么在2–sqrt(n)之间必定存在n的因数，那么最小的因数可能是合数吗? 答案是不可能，假设最小的因数是合数，那么，这个合数必定还有因数，这个合数就不可能是最小的因数。

所以找n的最小质因数，只要从2开始往上枚举，找到n的第一个因数就是n的最小质因数。

int n,ans; cin>>n; for(int i=2;i<=n;i++){ if(n%i==0){ ans=i; break; } } cout<<ans;