Hỏi về thuật toán phân tích thừa số nguyên tố

#1

Đề bài yêu cầu phân tích 1 số ra thành tích các thừa số nguyên tố ạ. Nhưng lại phải là số lớn nhân trước. VD: 999 = 37x3x3x3
Em tìm hiểu thì có 1 thuật toán, em cũng có code lại như vậy

    int main() {
    int n;
    int i = 2;
    cin >> n;
    while (n != 1)
    {
        if (n % i == 0)
        {
            cout << i <<"*";
            n /= i;
        }

        else
            i++;
    }

    return 0;
}

Code này chỉ có thể ra là 3x3x3x37. Cho em xin hỏi là có thể đảo ngược lại để thỏa với yêu cầu của đề không ạ

#2

lúc tìm được ước số thay vì xuất nó ra thì bỏ nó vô 1 mảng, xong xuôi xuất ngược mảng đó lại

với n là integer thì n dương tối đa là 231 - 1 nên có tối đa 31 thừa số nguyên tố. Lập cái mảng int thuaSoNgTo[31] là dư sức rồi.

#3 
void PhanTich(int n)
{
    for (int i = 2, count = 0; i <= n; i++)
        for (; n % i == 0; n /= i)
            cout << (count++ ? " * " : "") << i;
}
#4

Công nhận bài này thì cách dễ nhất là nhét vào mảng.
Một cách khác:

int biggest_prime(int n) {
    if (n <= 2) {
        return n;
    } else if (!(n & 1)) {
        return biggest_prime(n / 2);
    }
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) {
            return biggest_prime(n / i);
        }
    }
    return n;
}

void phan_tich(int n) {
    int biggest = biggest_prime(n);
    cout << n << " = " << biggest;
    n /= biggest;
    while (n > 1) {
        biggest = biggest_prime(n);
        cout << " x " << biggest;
        n /= biggest;
    }
    cout << endl;
}
#5

Cách của anh vẫn là in xuôi mà

1 Like
#6

Xuôi ngược gì chả được :v
Còn nếu muốn ngược thì sửa cái điều kiện trong vòng for lớn thôi, chứ đâu khó khăn gì :slight_smile:

#7

Sửa giúp em với ạ, em mới học thôi

#8

Tự vận động đi nhé :v cho code đến thế rồi mà con hỏi.

#9

Nếu sửa lại thì thuật toán sẽ bị sai ạ

#10

Debug đi.
Còn bí quá thì bạn tạo 1 mảng, lưu vào rồi đọc ngược giống như anh Trí nói ở post đầu đó

#11

Thuật toán này là xét i = 2 rồi lấy số n chia cho i tới khi không chia được thì tăng lên,
Cách đó em làm được rồi ạ

#12

app dung

#include<stdio.h>
void in(int i){
	if (i>10){
		in(i-1);
	}
	printf("%d\n",i);
}

int main(){
	in(20);
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?