Bài 1: Bài tập nghiên cứu

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 ≤ 109

Ví dụ: 

Số nhập vào là A	Số xuất ra là N
8	4
13	13

Phân tích:
Đây là một bài toán rất đơn giản nếu A là con số nhỏ, tuy nhiên do số A quá lớn nên việc tính theo các thông thường là điều rất khó thực hiện, do đó sẽ phải vận dụng nhiều tính chất số học để giải quyết bài toán tốt hơn.

Ý tưởng:
Ta vận dụng những tính chất sau:

Vậy ta phân tích A thành thừa số nguyên tố:

Ta thấy, nếu đơn giản nhất A chỉ phân tích thành 1 thừa số nguyên tố duy nhất, VD: A=2^k
Thì k lớn nhất có thể để còn nằm trong vùng giới hạn là 30
Vậy các số k lớn nhất chỉ co thể là 30.
Từ đó phân tích sô N hội đủ những yếu tố đó thì N^N chia hết cho A.

Code

#include <stdio.h>
#include <conio.h>
int a,n,t;
void tachsonguyento()
{
int j,i;
j=a;
t=1;
for (i=2;i*i<=j;i++)
{
if (j%i==0)
{
t*=i;
}
while (j%i==0) j/=i;
if (j==1) break;
}
t*=j;
}

void main()
{
int h,i,tam,j,k;
printf("Nhap vao so A \n");
scanf("%d",&a);
if (a==1)
printf("So can tim la %d", a);
else
{

tachsonguyento();
if (t<29)
{
for(h=1;h<=a;h++)
{
n=t*h;
k=1;
j=a;
for (i=2;i*i<=j;i++)
{
tam=0;
while(j%i==0)
{
j/=i;
tam++;
}
if (n<tam) k=0;
if ((j==1)||(k==0)) break;
}
if (k==1) break;
}
}
else n=t;
}
printf("So N can tim la: %d",n);
getch();
}