BÀI 1: Bài toán về số tự nhiên A và N^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=13Hướng dẫn giải:- nếu A là số nguyên tố thì dễ thấy N=A.
- 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;
}
}
}
}
}
|