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

nguyenquocphonng • 6:03 p.m. 29 Tháng 8, 2024 •
def prime_factors(n):
"""Trả về một danh sách các thừa số nguyên tố của n và số mũ của chúng"""
i = 2
factors = []
while i * i <= n:
count = 0
while (n % i) == 0:
n //= i
count += 1
if count > 0:
factors.append((i, count))
i += 1
if n > 1:
factors.append((n, 1))
return factors

def count_divisors(factors):
"""Tính số lượng ước số dựa trên thừa số nguyên tố"""
count = 1
for _, exp in factors:
count *= (exp + 1)
return count

def main():
import sys
input = sys.stdin.read
N = int(input().strip())
sai rồi bạn ê
# Phân tích thừa số nguyên tố
factors = prime_factors(N)

# Xuất kết quả phân tích thừa số nguyên tố factor_strings = [] for base, exp in factors: factor_strings.extend([str(base)] * exp) print('*'.join(factor_strings)) # Tính số lượng ước số divisors_count = count_divisors(factors) print(divisors_count)

if name == "main":
main()
-2
Phản hồi Chia sẻ

1 phản hồi

Code cho ai ko bt làm:
def prime_factorization(n):
factors = []
count = 0

# Phân tích số nguyên tố 2
while n % 2 == 0:
    factors.append(2)
    n //= 2
    count += 1

# Phân tích các số nguyên tố lẻ
for i in range(3, int(n**0.5) + 1, 2):
    while n % i == 0:
        factors.append(i)
        n //= i
        count += 1

# Nếu số nguyên tố còn lại là một số nguyên tố lớn hơn 2
if n > 2:
    factors.append(n)
    count += 1

return factors

def count_divisors(factors):
from collections import Counter
factor_count = Counter(factors)
num_divisors = 1
for count in factor_count.values():
num_divisors *= (count + 1)
return num_divisors

def main():
import sys
input = sys.stdin.read
n = int(input().strip())

factors = prime_factorization(n)
factor_string = '*'.join(map(str, factors))
num_divisors = count_divisors(factors)

print(factor_string)
print(num_divisors)

if name == "main":
main()

-1

Phản hồi

1 phản hồi

tk22dangminhduc • 9:43 p.m. 11 Tháng 7, 2023 •

một phiên bản dễ hơn của "FACTOR"...mãi vẫn chưa AC được bài đấy:")

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-11
Phản hồi Chia sẻ

hieuhfgr • 10:41 a.m. 3 Tháng 5, 2023 •

mình nghĩ bài này testcases đang yếu '-'

0
Phản hồi Chia sẻ

tienduyyl • 5:14 p.m. 15 Tháng 10, 2021 • ← đã chỉnh sửa →

i

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-5
Phản hồi Chia sẻ

phambinminh12345 • 5:44 p.m. 12 Tháng 10, 2021 •
Hint 1
Chia dần các ước nguyên tố của n đồng thời tăng biến đếm
Đưa các ước nguyên tố p và số lần bị chia vào một mảng Xuất các số nguyên tố theo tần số

Hint 2
Khi (p | n) thì p∗np=n
⇔p là ước của n thì np cũng là ước của n
Ta có thể chạy tới n−−√ để đếm số ước

Thay vì thử từng số nguyên tố, ta có thể từng số i tăng dần từ 2 và kiểm tra tính chia hết
Nếu n không chia hết i thì bỏ qua (vì nó không phải ước nguyên tố)

Ngược lại ta sẽ thêm số nguyên tố i vào mảng và chia n dần đồng thời tăng số lần chia

Hint 3
Có n=pf11×pf22×...×pfkk với fi∈N
Thì d=pf′′11×pf′′22×...×pf′′kk là ước của n ∀f′′i≤fi và f′′i∈N
Mỗi ước nguyên tố pi có f′′i cách chọn

Nên số cách chọn phần tử d là (f′′1+1)×(f′′2+1)×...×(f′′k+1)
Vậy khi phân tích số nguyên tố từ n ta dễ dàng tìm số ước trong O(log(logn))
Nhận xét rằng nếu với mọi số nguyên 2≤x≤√n không phải là ước của n thì n là số nguyên tố
Chạy tới √n hoặc tới khi n=1 để phân tích thừa số nguyên tố

Nếu sau đó n>1 thì n là số nguyên tố

Reference AC code | O(n−−√) time | O(lognlog(logn)) auxiliary space | Factorization
Copy
int main()
{
//// Input
int n = readInt();
int sqrtn = sqrt(n);

pair<int, int> divs; /// Divisors vector<p, f> = <prime divisor, frequency> /// p = 2 case if (n % 2 == 0) { divs.push_back(make_pair(2, 0)); /// Add new prime p = (2) do divs.back().se++, n /= 2; while (n % 2 == 0); } /// prime > 2 is odd, we dont have to care about even numbers for (int i = 3; i <= sqrtn; i += 2) { if (n % i != 0) continue; divs.push_back(make_pair(i, 0)); /// Add new prime p = (i) do divs.back().se++, n /= i; while (n % i == 0); if (n == 1) break; /// we can divide more } /// n is prime if (n > 1) divs.push_back(make_pair(n, 1)); /// Output int p = divs.size(); int count = 1; for (int i = 0; i + 1 < p; ++i) { count *= (divs[i].second + 1); while (divs[i].second-->0) cout << divs[i].first << '*'; } count *= (divs.back().second + 1); while (divs.back().second-->1) cout << divs.back().first << '*'; cout << divs.back().first << endl; cout << count; /// Number of divisors return 0;

}
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
-12
Phản hồi Chia sẻ

phambinminh12345 • 5:44 p.m. 12 Tháng 10, 2021 •
Hint 1
Chia dần các ước nguyên tố của n đồng thời tăng biến đếm
Đưa các ước nguyên tố p và số lần bị chia vào một mảng Xuất các số nguyên tố theo tần số

Hint 2
Khi (p | n) thì p∗np=n
⇔p là ước của n thì np cũng là ước của n
Ta có thể chạy tới n−−√ để đếm số ước

Thay vì thử từng số nguyên tố, ta có thể từng số i tăng dần từ 2 và kiểm tra tính chia hết
Nếu n không chia hết i thì bỏ qua (vì nó không phải ước nguyên tố)

Ngược lại ta sẽ thêm số nguyên tố i vào mảng và chia n dần đồng thời tăng số lần chia

Hint 3
Có n=pf11×pf22×...×pfkk với fi∈N
Thì d=pf′′11×pf′′22×...×pf′′kk là ước của n ∀f′′i≤fi và f′′i∈N
Mỗi ước nguyên tố pi có f′′i cách chọn

Nên số cách chọn phần tử d là (f′′1+1)×(f′′2+1)×...×(f′′k+1)
Vậy khi phân tích số nguyên tố từ n ta dễ dàng tìm số ước trong O(log(logn))
Nhận xét rằng nếu với mọi số nguyên 2≤x≤√n không phải là ước của n thì n là số nguyên tố
Chạy tới √n hoặc tới khi n=1 để phân tích thừa số nguyên tố

Nếu sau đó n>1 thì n là số nguyên tố

Reference AC code | O(n−−√) time | O(lognlog(logn)) auxiliary space | Factorization
Copy
int main()
{
//// Input
int n = readInt();
int sqrtn = sqrt(n);

pair<int, int> divs; /// Divisors vector<p, f> = <prime divisor, frequency> /// p = 2 case if (n % 2 == 0) { divs.push_back(make_pair(2, 0)); /// Add new prime p = (2) do divs.back().se++, n /= 2; while (n % 2 == 0); } /// prime > 2 is odd, we dont have to care about even numbers for (int i = 3; i <= sqrtn; i += 2) { if (n % i != 0) continue; divs.push_back(make_pair(i, 0)); /// Add new prime p = (i) do divs.back().se++, n /= i; while (n % i == 0); if (n == 1) break; /// we can divide more } /// n is prime if (n > 1) divs.push_back(make_pair(n, 1)); /// Output int p = divs.size(); int count = 1; for (int i = 0; i + 1 < p; ++i) { count *= (divs[i].second + 1); while (divs[i].second-->0) cout << divs[i].first << '*'; } count *= (divs.back().second + 1); while (divs.back().second-->1) cout << divs.back().first << '*'; cout << divs.back().first << endl; cout << count; /// Number of divisors return 0;

}
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
-8
Phản hồi Chia sẻ

minhtuanitk20 • 3:53 p.m. 1 Tháng 10, 2021 •

bài dễ nhất thế giới

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

-24
Phản hồi Chia sẻ

1 phản hồi

SPyofgame • 11:02 p.m. 10 Tháng 6, 2020 • ← chỉnh sửa 3 →
Spoiler Alert

Hint 1

Chia dần các ước nguyên tố của \(n\) đồng thời tăng biến đếm

Đưa các ước nguyên tố \(p\) và số lần bị chia vào một mảng
Xuất các số nguyên tố theo tần số

Hint 2

Khi \((p\ |\ n)\) thì \(p * \frac{n}{p} = n\)

\(\Leftrightarrow p\) là ước của \(n\) thì \(\frac{n}{p}\) cũng là ước của \(n\)

Ta có thể chạy tới \(\sqrt{n}\) để đếm số ước

Thay vì thử từng số nguyên tố, ta có thể từng số \(i\) tăng dần từ 2 và kiểm tra tính chia hết

Nếu \(n\) không chia hết \(i\) thì bỏ qua (vì nó không phải ước nguyên tố)

Ngược lại ta sẽ thêm số nguyên tố \(i\) vào mảng và chia \(n\) dần đồng thời tăng số lần chia

Hint 3

Có \(n = p_1 ^ {f_1} \times p_2 ^ {f_2} \times ... \times p_k ^ {f_k}\) với \(f_i \in N\)

Thì \(d = p_1 ^ {f''_1} \times p_2 ^ {f''_2} \times ... \times p_k ^ {f''_k}\) là ước của \(n\) \(\forall f''_i ≤ f_i\) và \(f''_i \in N\)

Mỗi ước nguyên tố \(pi\) có \(f''_i\) cách chọn

Nên số cách chọn phần tử \(d\) là \((f''_1 + 1) \times (f''_2 + 1) \times ... \times (f''k + 1)\)

Vậy khi phân tích số nguyên tố từ \(n\) ta dễ dàng tìm số ước trong \(O(log (log n))\)

Nhận xét rằng nếu với mọi số nguyên \(2 ≤ x ≤ √n\) không phải là ước của \(n\) thì \(n\) là số nguyên tố

Chạy tới √n hoặc tới khi \(n = 1\) để phân tích thừa số nguyên tố

Nếu sau đó \(n > 1\) thì \(n\) là số nguyên tố

Reference AC code | \(O(\sqrt n)\) time | \(O(\frac{\log n}{\log(\log n)})\) auxiliary space | Factorization

C++
int main() { //// Input int n = readInt(); int sqrtn = sqrt(n); pair<int, int> divs; /// Divisors vector<p, f> = <prime divisor, frequency> /// p = 2 case if (n % 2 == 0) { divs.push_back(make_pair(2, 0)); /// Add new prime p = (2) do divs.back().se++, n /= 2; while (n % 2 == 0); } /// prime > 2 is odd, we dont have to care about even numbers for (int i = 3; i <= sqrtn; i += 2) { if (n % i != 0) continue; divs.push_back(make_pair(i, 0)); /// Add new prime p = (i) do divs.back().se++, n /= i; while (n % i == 0); if (n == 1) break; /// we can divide more } /// n is prime if (n > 1) divs.push_back(make_pair(n, 1)); /// Output int p = divs.size(); int count = 1; for (int i = 0; i + 1 < p; ++i) { count *= (divs[i].second + 1); while (divs[i].second-->0) cout << divs[i].first << '*'; } count *= (divs.back().second + 1); while (divs.back().second-->1) cout << divs.back().first << '*'; cout << divs.back().first << endl; cout << count; /// Number of divisors return 0; }
31
Phản hồi Chia sẻ

1 phản hồi