Phân tích thừa số nguyên tố

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Xem hướng dẫn

Tác giả:

corona

Dạng bài

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho số nguyên dương \(N\).

Yêu cầu: Hãy phân tích \(N\) thành thừa số nguyên tố và đếm ước số của \(N\).

Input

Gồm một dòng duy nhất chứa số nguyên dương \(N\).

Output

Dòng thứ nhất ghi phân tích thừa số của \(N\) dưới dạng \(a * b * c * d\), với \(a, b, c, d\) là các thừa số nguyên tố của \(N\).
Dòng thứ hai ghi số lượng ước số của \(N\).

Constraints

\(N\leq 2.10^9\)

Example

Test 1

Input

Output

2*5
4

Test 2

Input

Output

2*2*5*5
9

Bình luận

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    vector<int> powvec;
    vector<int> prime_fact;
    cin >> n;
    if (n == 1) {
        prime_fact.push_back(1);
        powvec.push_back(1);
    }

    for (int i = 2; i * i <= n; i++) {
        int alpha = 0;
        if (n % i == 0) {
            while (n % i == 0) {
                alpha++;
                n /= i;
                prime_fact.push_back(i);
            }
        }
        powvec.push_back(alpha);
    }

    if (n != 1) {
        powvec.push_back(1);
        prime_fact.push_back(n);
    }

    int counter = 1;
    for (auto i : powvec) {
        counter *= (i + 1);
    }
    // out
    for (int i = 0; i < prime_fact.size(); i++) {
        if (i != prime_fact.size() - 1) cout << prime_fact[i] << "*";
        else cout << prime_fact[i] << "\n";
    }
    cout << counter;
}

Video tham khảo:

Phản hồi

9 bình luận nữa