1059 Prime Factors (25 分)
Given any positive integer , you are supposed to find all of its prime factors, and write them in the format = .
Input Specification:
Each input file contains one test case which gives a positive integer in the range of long int.
Output Specification:
Factor in the format =
^
*
^
*
…*
^
, where ‘s are prime factors of in increasing order, and the exponent is the number of — hence when there is only one , is 1 and must NOT be printed out.
Sample Input:
97532468
Sample Output:
97532468=2^2*11*17*101*1291
题目解读:把一串数字进行因式分解,对重复的素数要用指数的表达方式。
解题思路:很简单的暴力算法,因为只有一个数字也不需要剪枝就可以得出结果。map很适合做这种有固定顺序的,需要记数的题。
这次做题有一些误区,比如map中对value的加法应该用prime[i]++而不是prime.at(i)++。
还有对循环的判断应该是小于NUM而不是它的平方根,还好这道题通过很小的数就可以看出哪里错了,没有long int的溢出问题。
AC代码:
- #include <iostream>
- #include <algorithm>
- #include <map>
- using namespace std;
- bool isPrime( long int n ){
- if (n == 1) return false;
- for (long int i = 2; i <= sqrt(n); i++) {
- if (n % i == 0)return false;
- }
- return true;
- }
- int main()
- {
- long int num;
- map<long int,int> primetime;
- cin >> num;
- cout << num << "=";
- int flag = 1;
- while (num != 1 && flag == 1) {
- flag = 0;
- for (long int i = 2; i <= num; i++) {
- if (isPrime(i) && num % i == 0) {
- primetime[i]++;
- num = num/i;
- flag = 1;
- break;
- }
- }
- }
- if (primetime.size() == 0) {
- cout <<"1*"<< num << endl;
- }
- int count = 1;
- for (auto value : primetime) {
- if (value.second != 1)
- cout << value.first << "^" << value.second;
- else cout << value.first;
- if (count < primetime.size())
- cout << "*";
- count++;
- }
- }
0 条评论