BÀI 1: Bài toán về số tự nhiên A và N^N.
Chia sẻ đến

Mã số tài liệu: 6571
Đơn giá: 0
NHẤN VÀO ĐỂ TẢI

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^9
Ví dụ:
Số nhập vào là A  Số xuất ra là N:
A=8 thì N=4
A=13 thì N=13

Hướng dẫn giải:
  1. nếu A là số nguyên tố thì dễ thấy N=A.
  1. Nếu A không nguyên tố thì ta phân tích A ra tích các thừa số nguyên tố.
A = x[1]^a[1] * x[2]^a[2] *  ... * x[m]^a[m] .do đó N có dạng x[1] *x[2]*..*x[n]*Cvì A<2^30 nên C<30. ta thư lân lượt các giá trị của C để tìm C nhỏ nhất.tuy nhiên cần chú ý các trường hợp A=2^m hay 3^m.cần xét riêng.vì khí C=4 thì nó sẽ trùng lại với 2.tương tự với 3.Dưới đây mình xin trình bày một đoạn code để giải bài toán trên:

#include <stdio.h>
#include <math.h>
int SNT(int a);
int SNT(int a)
{
int t = 1;
for(int i = 2 ; i < sqrt ((float)a ) ; i++ )
{
if (a % i == 0)

t = 0;
break;
}
}
return t;
}
void main()
{
int A  ,N = 1 ;
printf(" nhap A= ") ;
scanf(" %d",&A) ;
if( SNT(A) == 1 )
printf("so N can tim la %d \n", A ) ;
else
{
float mu = 1;
for( int i = 2 ; i <= A ; i++ )
{
if(A == 1)
break;
int j = 0;
if (A % i == 0 )
{
N = N * i;
while(A % i == 0 )
{
A = A/i ;
j = j  +1 ;
}
if(mu< j)
mu  = j;
}
}
int n = N , i ;
switch(n)
{
case 2:
for( i = 2 ; i < 30 ; i++)
{
n = n*2;
if( mu/i < n )
{
printf("so N can tim la: %d\n",n);break;
}
}
break;
case 3:
for( i=2 ; i<30 ; i++ )
{
n = n*3 ;
if(mu/i <n )
{
printf("so N can tim la: %d\n",n);break;
}
}
break;
default:
for( int  i= 1 ; i <=30 ; i++ )
{
n= N*i ;
if( n> mu ) {
printf("so N can tim la: %d\n",n);break;
}
}
}
}
}