Tìm số nguyên nhỏ nhất để tích chữ số bằng số nhập vào

[nhaths4701 (Bùi Đức Nhật)]

Mọi người cho em xin ý tưởng để giải bài này với ạ, em cảm ơn nhiều ạ!

[anon12276517]

Duyệt từ 9 ==> 2 để phân tích thừa số của nó là được

Gợi ý cho bạn :)

    String out;
    for(int i = 9; i >= 2; i--)
    {        
        while(product % i == 0)
        {
            product /= i;
            out += i;
        }        
    }

[nhaths4701 (Bùi Đức Nhật)]

Cái này đâu liên quan đến thừa số nguyên tố đâu ạ?

[rogp10]

Đúng là ko cần nguyên tố, mà phân tích như bạn trên ấy.

[nhaths4701 (Bùi Đức Nhật)]

Các bác cho em hỏi chút nữa với, e cũng đã code theo ý tưởng bác NDA từ trước rồi, cơ mà những số như 25 hay 16 sẽ không tính được, bởi nó không nhận ra 2 số ^2 hay ^3, cho em solution với ạ!

[rogp10]

1. Bạn chia tới 9 mà ko về 1 tức là false được rồi ko cần prime.
2. Rõ ràng thì tích 16 ta lấy 2*8 tốt hơn 4*4

[nhaths4701 (Bùi Đức Nhật)]

vâng 16 e nghĩ sai, còn 25 thì sao ạ?

[anon12276517]

Đáp án là 55 đó bạn

[nhaths4701 (Bùi Đức Nhật)]

Em biết là 55, nhưng code của em nó không in ra được những cái có 2 số giống nhau thì làm thế nào ạ?
Code của em đây ạ:

#include<stdio.h>
#include<math.h>
int digitsProduct(int product);
int is_prime(int n);
int main()
{
    printf("Nhap n: ");
    int n;
    scanf("%d",&n);
    printf("%d",digitsProduct(n));
}
int is_prime(int n)
{
    for (int i=2;i<=sqrt(n);++i)
    {
        if (n%i == 0)
        return 0;
    }
    return 1;
}
int digitsProduct(int product)
{
    if (product==0)
    return 10;
    if (product<=10)
    return product;
    if (is_prime(product))
    return -1;
    int i=9, j=-1, res=0;
    int a[j];
    while (i>=2)
    {
        if (product%i == 0)
        {
            j++;
            a[j] = i;
            product /= i;
        }
        --i;
    }
    if (j==-1)
    return -1;
    for (int k=j; k>=0;--k)
    {
        res = res*10 + a[k];
    }
    return res;
}

[anon12276517]

Nó có liên quan gì đến thừa số nguyên tố đâu nhỉ ?? Chỉ cần duyệt từ 9 ==> 2 rồi cộng chuỗi thôi mà @@ Xem đoạn bên trên mình viết ý

    String out;
    for(int i = 9; i >= 2; i--)
    {        
        while(product % i == 0)
        {
            product /= i;
            out += i;
        }        
    }

[nhaths4701 (Bùi Đức Nhật)]

Ý của em là khi số đấy là số nguyên tố thì return luôn cái số đó, để chạy những số lớn mà không cần phân tích ấy @@

[anon12276517]

Cộng chuỗi xong parse từ chuỗi sang int thử xem bạn. Code bạn hơi rối @@

[rogp10]

để chạy những số lớn mà không cần phân tích

Lúc đó bạn vẫn đang phân tích đấy
Những cách không qua phân tích không dễ như vậy (nhất là cách chính xác - gần đúng 99.99% dễ hơn).

[nhaths4701 (Bùi Đức Nhật)]

Thank các bác, em tìm ra lỗi của em rồi, ở vòng while (i>=2) em phải làm tiếp vòng lặp mới đúng lại đi để if. Code hoàn chỉnh của em đây ạ, mọi người tham khảo ^^!

#include<stdio.h>
#include<math.h>
int digitsProduct(int product);
int is_prime(int n);
int main()
{
    printf("Nhap n: ");
    int n;
    scanf("%d",&n);
    printf("%d",digitsProduct(n));
}
int digitsProduct(int product)
{
    if (product==0)
    return 10;
    if (product<=10)
    return product;
    int i=9, j=-1, res=0;
    int a[50];
    while (i>1)
    {
        while (product%i == 0)
        {
            j++;
            a[j] = i;
            product /= i;
        }
        --i;
    }
    if ((j==-1)||(product>=10))
    return -1;
    for (int k=j; k>=0;--k)
    {
        res = res*10 + a[k];
    }
    return res;
}

[rogp10]

Bạn vui lòng đọc nhé

Cách post Code dùng Markdown trong Category Programming

Làm sao để có thể hiển thị syntax highlighting bằng markdown? Các bạn phải đánh dấu ``` như ví dụ dưới đây Chú ý, dấu ``` được tạo ra bởi nút nằm bên trái số 1 trên bàn phím, nút này sẽ là ~ khi bấm giữ Shift Ví dụ cho C Nội dung: ``` void main() { } ``` Và đừng quên ``` ở cuối Kết quả void main() { } Ví dụ cho Pascal Nội dung: ``` Program HelloWorld; Begin WriteLn('Hello world!') {no ";" is required after the last statement of a block - adding one adds a "null statement" to t…

[nhaths4701 (Bùi Đức Nhật)]

Em cảm ơn ạ, do em mới tham gia cộng đồng này nên không biết cách ạ !

[907pqv (Violet)]

nhưng phân tích thành thừa số nguyên tố vẫn giải ra đúng ko a?

[nhaths4701 (Bùi Đức Nhật)]

Theo em là không bác ạ!

[rogp10]

Bài này thì không tới đâu cả

Để thừa số còn lại nhỏ nhất thì ta sẽ chia cho số lớn nhất có thể được. Như vậy khi có phân tích thành thừa số thì ta tách từng bộ 3 thừa số 2 và 2 thừa số 3, sau đó chia trường hợp còn lại hơi phức tạp.