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代码:

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <map>
  4. using namespace std;
  5. bool isPrime( long int n ){
  6. if (n == 1) return false;
  7. for (long int i = 2; i <= sqrt(n); i++) {
  8. if (n % i == 0)return false;
  9. }
  10. return true;
  11. }
  12. int main()
  13. {
  14. long int num;
  15. map<long int,int> primetime;
  16. cin >> num;
  17. cout << num << "=";
  18. int flag = 1;
  19. while (num != 1 && flag == 1) {
  20. flag = 0;
  21. for (long int i = 2; i <= num; i++) {
  22. if (isPrime(i) && num % i == 0) {
  23. primetime[i]++;
  24. num = num/i;
  25. flag = 1;
  26. break;
  27. }
  28. }
  29. }
  30. if (primetime.size() == 0) {
  31. cout <<"1*"<< num << endl;
  32. }
  33. int count = 1;
  34. for (auto value : primetime) {
  35. if (value.second != 1)
  36. cout << value.first << "^" << value.second;
  37. else cout << value.first;
  38. if (count < primetime.size())
  39. cout << "*";
  40. count++;
  41. }
  42. }
#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 条评论

发表评论

Avatar placeholder