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

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

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Cho số nguyên dương ~n~. Hãy phân tích ~n~ ra thừa số nguyên tố. Tức là tìm các số nguyên tố ~p_1, p_2, …, p_k~ đôi một phân biệt và các số nguyên dương ~α_1, α_2, …, α_k~ sao cho:$$n = {p_1}^{{\alpha _1}} \times {p_2}^{{\alpha _2}} \times ... \times {p_k}^{{\alpha _k}}$$

Input

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

Giới hạn:

~1 ≤ n ≤ 10^{12}~.

Output

Dòng đầu ghi số nguyên dương ~k~
~k~ dòng sau, dòng thứ ~i~ ghi hai số ~p_i~ và ~α_i~ cách nhau một dấu cách, các số ~p_i~ được sắp xếp tăng dần.

Sample

Input #1

Output #1

2
2 1
5 1

Input #2

Output #2

2
2 2
3 1

Hint

~10 = 2^1 × 5^1~
~12 = 2^2 × 3^1~

Problem source: Chuyên Sơn La Online Judge

Bình luận

Hãy đọc nội quy trước khi bình luận.

c++ full ac

#include <iostream>
#include <math.h>
#include <map>

using namespace std;
using ll = long long;

void phantich(ll n) {
    int i,d,cnt = 0;
    map<int,int> a;
    for (i = 2; i <= sqrt(n); i++){
        int d = 0;
        while (n % i == 0){
            n /= i;
            d++;
        }
        if (d){
            cnt++;
            a[i] = d;
        }
    }
    if (n != 1){
        a[n] = 1;
        cnt++;
    }
    cout << cnt << endl;
    for (auto x : a){
        cout << x.first << ' ' << x.second << endl;
    }
}

int main() {
    ll n;
    cin >> n;
    phantich(n);
    return 0;
}

-7

hz001 đã bình luận lúc 19, Tháng 2, 2024, 1:27 ← chỉnh sửa →

bài khá dễ :))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

import java.util.Scanner; import java.util.Vector;

public class PRIMFAC { public static void main(String[] args) { Scanner sc = new Scanner(System.in);

    long n = sc.nextLong(), i = 2, k = 0, d = 0;
    Vector<Long> p = new Vector<Long>();
    Vector<Long> a = new Vector<Long>();
    while (n > 1) {
        if (n % i == 0) {
            d++;
            n /= i;
        } else {
            if (d != 0) {
                p.add(i);
                a.add(d);
                d = 0;
                k++;
            }
            while(n % i != 0) i++;
        }
    }
    if (d != 0) {
        p.add(i);
        a.add(d);
        k++;
    }
    System.out.println(k);
    for (int j = 0; j < p.size(); j++) {
        System.out.println(p.elementAt(j) + " " + a.elementAt(j));
    }

    sc.close();
}

}

n = int(input()) d = {}

i = 2

while n != 1:

if n%i == 0:

    n //= i

    if i not in d:

        d[i] = 1

    else:

        d[i] += 1

else:

    i += 1

print(len(d))

for i in d:

print(i,d[i])

1

Methamphetamin đã bình luận lúc 26, Tháng 1, 2024, 20:00

.

1

Aothatday đã bình luận lúc 17, Tháng 1, 2024, 14:39

code tham khảo đây :v https://www.ideone.com/koknvZ

-5

luongptit đã bình luận lúc 17, Tháng 12, 2023, 18:01

:( sai 1 test kỳ quá

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

kingofcode888 đã bình luận lúc 8, Tháng 11, 2023, 13:42

hay quas

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-3

kingofcode888 đã bình luận lúc 8, Tháng 11, 2023, 13:41 ← chỉnh sửa →

hay

0

vdtue đã bình luận lúc 13, Tháng 9, 2023, 13:38

Sao test 1 ảo v, 102 thì phải in ra: 2 1 \n 3 1 \n 17 1 mà hình như test là: 2 2