main

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

Phân tích thừa số nguyên tố là cách biểu diễn số tự nhiên N dưới dạng tích các thừa số nguyên tố, cách biểu diễn này là duy nhất với số tự nhiên N

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

Xét thấy các thừa số nguyên tố d của hợp số N không thể đều lớn hơn √N. 

Vì thế bạn chỉ cần xét các thừa số nguyên tố trong đoạn [2, √N] và thử chia 

Phương pháp này tương đối khó hiểu, bạn xem video bài giảng của mình sẽ có giải thích chi tiết hơn.

Thuật toán Trial division :

1.  Duyệt các số d từ 2 tới √N
2. Nếu N chia hết cho d thì tiến hành lấy N chia cho d cho tới khi còn chia hết
3. Sau khi duyệt xong các số từ 2 tới √N mà N vẫn khác 1 thì N chính là thừa số nguyê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++){
      //Neu n chia het cho i, i se la thua so nguyen to
      while(n % i == 0){
         printf("%d ", i);
         n /= i; // n se giam 
      }
   }
   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 cách thêm dấu x giữa các thừa 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; 
         //Nếu vẫn còn thừa số phía sau
         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 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; // n se giam 
         ++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 nguyên tố của N

Để liệt ước nguyên tố của N, cách đơn giản nhất bạn làm là viết 1 hàm số nguyên tố sau đó duyệt các ước của N và kiểm tra, nhưng thực ra ước nguyên tố chính là thừa số nguyên tố.

Vậy nên khi làm các bài toán liên quan tới ước nguyên tố của 1 số nguyên bạn phải nghĩ ngay tới phân tích thừa số nguyên tố. 

Mình sẽ trình bày 2 cách, cách 1 sẽ không tối ưu bằng cách 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 bài giảng của mình về Phân Tích Thừa Số Nguyên Tố

hQUUTcDr_5c