[C]. Phân Tích Thừa Số Nguyên Tố

Trong bài học kinh nghiệm này những các bạn sẽ học tập cơ hội phân tách số vẹn toàn N trở nên quá số nhân tố, đó là một kỹ năng và kiến thức khó khăn yên cầu bạn phải nắm rõ kỹ năng và kiến thức về số nhân tố trước đó

NỘI DUNG : 

• Phân Tích Thừa Số Nguyên Tố
• Các Bài Toán 
• Video Tutorial 

  ---

main

1.Phân Tích Thừa Số Nguyên Tố

Phân tích quá số nhân tố là cơ hội trình diễn số đương nhiên N bên dưới dạng tích những quá số nhân tố, cơ hội trình diễn này là có một không hai với số đương nhiên N

Ví dụ N = 60 = 2 x 2 x 3 x 5

Xét thấy những quá số nhân tố d của hợp ý số N ko thể đều to hơn √N. 

Vì thế chúng ta chỉ việc xét những quá số nhân tố trong khúc [2, √N] và demo chia 

Phương pháp này kha khá khó khăn hiểu, chúng ta coi video clip bài bác giảng của tớ sẽ có được phân tích và lý giải cụ thể rộng lớn.

Thuật toán Trial division :

1.  Duyệt những số d kể từ 2 cho tới √N
2. Nếu N phân chia không còn cho tới d thì tổ chức lấy N phân chia cho tới d cho đến lúc còn phân chia hết
3. Sau Lúc duyệt xong xuôi những số kể từ 2 cho tới √N tuy nhiên N vẫn không giống 1 thì N đó là quá số nhân tố cuối cùng 

Code : 

#include "stdio.h"
#include "math.h"

void factorize(int n){
   for(int i = 2; i <= sqrt(n); i++){
      
      while(n % i == 0){
         printf("%d ", i);
         n /= i; 
      }
   }
   if(n > 1){
      printf("%d", n);
   }
}

int main(){
   factorize(60);
   return 0;
}

Output :

2 2 3 5

2.Các Bài Toán

Bài 1. Phân tích bằng phương pháp thêm thắt vết x trong những quá số

Ví dụ : N = 60 = 2 x 2 x 3 x 5

#include "stdio.h"
#include "math.h"

void factorize(int n){
   for(int i = 2; i <= sqrt(n); i++){
      while(n % i == 0){
         printf("%d", i);
         n /= i; 
         
         if(n > 1){
            printf(" x ");
         }
      }
   }
   if(n > 1){
      printf("%d", n);
   }
}

int main(){
   factorize(60);
   return 0;
}

Output : 

2 x 2 x 3 x 5

Bài 2. Phân tích TSNT kèm cặp số mũ

Ví dụ : N = 60 = 2^2 x 3^1 x 5^1

#include "stdio.h"
#include "math.h"

void factorize(int n){
   for(int i = 2; i <= sqrt(n); i++){
      int mu = 0;
      while(n % i == 0){
         n /= i; 
         ++mu;
      }
      if(mu != 0){
         printf("%d^%d", i, mu);
         if(n > 1){
            printf(" x ");
         }
      }
   }
   if(n > 1){
      printf("%d^1", n);
   }
}

int main(){
   factorize(60);
   return 0;
}

Output :

2^2 x 3^1 x 5^1

Bài 3. Liệt kê ước nhân tố của N

Để liệt ước nhân tố của N, cơ hội giản dị nhất chúng ta thực hiện là ghi chép 1 hàm số nhân tố tiếp sau đó duyệt những ước của N và đánh giá, tuy nhiên thực đi ra ước nhân tố đó là quá số nhân tố.

Vậy nên những khi thực hiện những câu hỏi tương quan cho tới ước nhân tố của một số vẹn toàn chúng ta cần nghĩ về tức thì cho tới phân tách quá số nhân tố. 

Mình tiếp tục trình diễn 2 cơ hội, cơ hội 1 sẽ không còn tối ưu bằng phương pháp 2. 

Cách 1 : Code ngây thơ

#include "stdio.h"
#include "math.h"

int prime(int n){
   if(n < 2) return 0;
   for(int i = 2; i <= sqrt(n); i++){
      if(n % i == 0){
         return 0;
      }
   }
   return 1;
}

void prime_divisor(int n){
   for(int i = 1; i <= n; i++){
      if(n % i == 0 && prime(i)){
         printf("%d ", i);
      }
   }
}

int main(){
   prime_divisor(60);
   return 0;
}

Cách 2 : Code tối ưu

#include "stdio.h"
#include "math.h"

void prime_divisor(int n){
   for(int i = 2; i <= sqrt(n); i++){
      if(n % i == 0){
         printf("%d ", i);
         while(n % i == 0){
            n /= i;
         }
      }
   }
   if(n > 1){
      printf("%d\n", n);
   }
}

int main(){
   prime_divisor(60);
   return 0;
}

Output : 

2 3 5

Xem thêm thắt bài bác giảng của tớ về Phân Tích Thừa Số Nguyên Tố

hQUUTcDr_5c