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

Phân tích thừa số nguyên tố là một cách biểu diễn số tự nhiên N dưới dạng tích của các thừa số nguyên tố. Đây là cách biểu diễn duy nhất và độc nhất với số N. Ví dụ, giá trị N = 60 có thể được phân tích thành tích của các thừa số nguyên tố là 2 x 2 x 3 x 5.

Có thể bạn quan tâm

Để phân tích thừa số nguyên tố, ta chỉ cần xét các thừa số trong đoạn từ 2 đến căn bậc hai của số N. Ta thử chia số N cho các thừa số này và tiếp tục chia cho tới khi không còn chia hết được nữa.

Bạn đang xem: [C]. Phân Tích Thừa Số Nguyên Tố

Phương pháp này có thể khá khó hiểu, bạn có thể xem video bài giảng ở dưới để có giải thích chi tiết hơn.

Contents

1 Thuật toán Trial division
2 Các Bài Toán

Thuật toán Trial division

Duyệt các số d từ 2 tới căn bậc hai của N.
Nếu N chia hết cho d, tiến hành lấy N chia cho d cho tới khi không còn chia hết nữa.
Sau khi duyệt xong các số từ 2 tới căn bậc hai của N mà N vẫn khác 1, thì N chính là thừa số nguyên tố cuối cùng.

Dưới đây là đoạn code minh họa:

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

void factorize(int n){
  for(int i = 2; i <= sqrt(n); i++){
    // Nếu n chia hết cho i, i sẽ là thừa số nguyên tố
    while(n % i == 0){
      printf("%d ", i);
      n /= i; // n sẽ giảm
    }
  }

  if(n > 1){
    printf("%d", n);
  }
}

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

Output:

2 2 3 5

Bài 1: Phân tích bằng cách thêm dấu x giữa các thừa số

Để phân tích số N thành tích các thừa số nguyên tố và thêm dấu x giữa chúng, ta có thể sử dụng đoạn code sau:

#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 thừa số nguyên tố kèm số mũ

Để phân tích số N thành tích các thừa số nguyên tố kèm theo số mũ, ta có thể sử dụng đoạn code sau:

#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);

      // Nếu vẫn còn thừa số phía sau
      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

Xem thêm : Top 10 Bài văn đề xuất về sự lựa chọn nghề nghiệp tương lai (lớp 12) tuyệt vời nhất

Để liệt kê tất cả các ước nguyên tố của N, ta có thể sử dụng hai cách sau:

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("%dn", n);
  }
}

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

Output: