2016-08-13

UVA - 10392 Factoring Large Numbers

题目大意：求n的所有因数。

解题思路：可以直接暴力不断从2开始跑，遇到能整除的就整除，然后再从2开始跑。

注意：如果循环中直接让 i 从 2 循环到 n 的话，会 TLE 。所以必须得优化算法，这里选择让 i 从 2 循环到 sqrt(n) 处，可以大大节省时间。

#include <iostream> #include <cstdio> #include <cmath> using namespace std; int main() { long long n; while ( scanf("%lld", &n) && n > 0 ) { for ( long long i = 2; i <= sqrt(n); i++) { if ( n % i == 0 ) { printf(" %lld\n", i); n /= i; i = 2; } } printf(" %lld\n", n); cout << endl; } return 0; }