Bài tập 01

Đề bài 1: 

Cho số tự nhiên A. Hãy tìm số tự nhiên N nhỏ nhất sao cho N lũy thừa N (nhân N cho chính nó N lần) chia hết cho A. Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị: 1 ≤ A ≤ 10⁹

Vd:
A=8 thì N=4
A=13 thì N=13

Phân tích:

Chúng ta đều biết mỗi một số  tự nhiên đều phân tích được thành tích của các thừa số nguyên tố. Để  N^N chia hết cho A thì Nⁿ cũng  phải chứa các thừa số nguyên tố tạo nên A. Mặc khác số yêu cầu tìm là Nⁿ do đó N chỉ cần chứa các thừa số nguyên tố tạo nên A (gọi là M) , thoả :
TH1: M  >=  A à N chia hết cho A à N^N chia hết cho A
Vd:
A = 6 = 2.3
N = M= 2.3
Nⁿ  chia hết cho A
TH2: M  < A
Vậy ta cần tìm một số i nào đó sao cho i*M là số nhỏ nhất  thoả: i*M = N và  Nⁿ chia hết cho A.
Mà N^N = (iM)^iM do đó để tìm số N nhò nhất thoả yêu cầu thì iM >= max{ mũ của các thừa số nguyên tố trong A} (TH1 i=1).
Vd:
A = 8 = 2³
M=2 < 8
Chọn i=2 à iM = N = 4 > 3 à N^N = 4⁴  chia hết cho 8

Kết luận:

Đầu tiên ta tìm số M chứa các thừa số nguyên tố có trong A.
Sau đó, là tìm số mũ cao nhất của thừa số của A.
Nếu M>= A:  N=M.
Nếu M<A:  tìm i sao cho iM > max {số mũ của thừa số nguyên tố trong A}.

Code: (Đây chỉ là đoạn code để phân tích vấn đề trên, không phải là một bài code hoàn chỉnh để chạy chương trình...)

....

long tinhM(long a)
{
    long m=1;int i=2;
    while (a>1)
    {
        while (a%i==0)
        {
             while (a%i==0)
             {
                 a=a/i;
             }
             m = m*i;
        }
        i=i+1;
    }
    return m;
}
int tinhSoMu(long a)
{
    int somu;int max=1;int i=2;
    while (a>1)
    {
        somu=0;
        while (a%i==0)
        {
            a= a/i;
            somu = somu+1;
        }
        if ( max< somu)
            max = somu;
         i=i+1;
    }
    return max;
}
int timi(long m, int somu)
{
    int i=1;
    while (m < somu)
    {
        if ((m*i) >= somu)
           break;
       i=i+1;
    }
    return i;
}

......