P1075 质因数分解
假期第一天就给一道入门难度的题写题解……
这道题一开始就被我想复杂了：埃式筛，欧拉筛……然而开一个1e9的数组？不现实。
直到看到题解区的dalao用唯一分解定理：
算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1^a1*P2^a2*P3^a3......*Pn^an，这里P1<P2<P3......<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。最早证明是由欧几里得给出的。
——百度百科
那么题目要求最后一个素数，那么找到第一个素数，再用n除以它就可以了。
n%第一个素数恰好=0，那么只要找到第一个可以被n整除的数就可以，无需筛素数哦。
AC代码：
#include<bits/stdc++.h> using namespace std; int n,p; int main() { scanf("%d",&n); for(int i=2;i<=n;i++) if(n%i==0) { printf("%d",n/i); return 0; } } View Code
转载于:https://www.cnblogs.com/yige2019/p/11256387.html
相关资源：NOIP2012年普及组复赛试题第1题《质因数分解》测试数据10组