Phân tích thừa số nguyên tố bằng ngôn ngữ C/C++

0
3549
phan tich thua so nguyen to trong c

Bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++ là một bài toán lập trình khá hay. Trong bài viết hôm nay, mình sẽ giới thiệu cho bạn đọc cách giải bài toán này

1. Số nguyên tố là gì? Phân tích thừa số nguyên tố là như thế nào?

Số nguyên tố là số chỉ chia hết cho 1 và chính nó.

Ví dụ: 2, 3, 5, 7. . .

Phân tích thừa số nguyên tố tức là phân tích một số nguyên cho trước thành tích của các số nguyên tố.

Ví dụ: 20 phân tách thành 2*2*5
30 phân tách thành 2*3*5

2. Bài toán phân tích thừa số nguyên tố của số nguyên n

Đề bài: Nhập vào số nguyên n từ bàn phím n>1, in ra màn hình dãy các số nguyên tố được phân tách bởi số nguyên n sắp xếp theo chiều tăng dần, mỗi số cách nhau một dấu cách.

Ví dụ:

Đầu vàoĐầu ra
122 2 3
Đầu vàoĐầu ra
93 3

Tích của các số ở kết quả của bài toán chính là số nguyên ban đầu được nhập vào từ bàn phím.

3. Giải quyết bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++

3.1 Giới thiệu thuật toán

Thuật toán đưa ra dựa trên phương pháp chia lần lượt cho các số nguyên tố nhỏ hơn N theo chiều từ nhỏ đến lớn. Tức là chia cho số nguyên tố nhỏ nhất, nếu phép chia hết, chúng ta nhận 1 giá trị, kết quả của phép chia sẽ gán thành N, nếu không chia hết, chúng ta tiếp tục chia giá trị N cho số nguyên tố lớn hơn.

Để thực hiện được việc chia cho các số nguyên tố từ nhỏ đến lớn, ta cho N chia cho các số lần lượt tử 2 đến N, thuật toán sẽ bỏ qua số không phải là số nguyên tố (n) vì số không phải là số nguyên tố sẽ chia hết cho số nguyên tố nhỏ hơn nó(n), do đó đương nhiên N sẽ chia hết cho số nguyên tố nhỏ hơn (n) nào đó.

Chúng ta cần khai báo một mảng để lưu giá trị mỗi lần N chia hết cho số đó.

3.2 Code trong C

Code trong C và C++ chỉ khác nhau một số cấu trúc cơ bản, về mặt thuật toán thì không có gì khác biệt.

Nhìn vào thuật toán mình chia sẻ có vẻ hơi khó hiểu, bạn hãy nhìn vào những dòng code dưới đây để hiểu chi tiết hơn nhé!

#include<stdio.h>

void thuasonguyento(long &amp;n){

	scanf("%d",&amp;n);

	long a[100000]; //mang a de dung gia tri

	long c=0;

	while(n>1){

	for(long i=2;i<=n;i++){

		while(n%i==0){ //neu n chia het cho i thi lay gia tri i

			n=n/i;

			a=i;

			c++;    //them gia tri thi phai tang c

		}
	}

	}
	
	for(long i=0;i<c;i++){ // dinh dang in ra man hinh thoi hiha

		if(i!=c-1)

			printf("%d ",a[i]);

		if(i==c-1)

			printf("%d",a[i]);
	}

}
int main(){

	long n;

	thuasonguyento(n); //goi ham ra ne

	return 0;
}

Kết quả chạy thử:

3.3 Code trong C++

C++ là nâng cao của C nên cấu trúc có khác một chút.

#include<iostream>

using namespace std;

void thuasonguyento(long &amp;n){

	cin>>n;

	long a[100000];

	long c=0;

	while(n>1){

	for(long i=2;i<=n;i++){

		while(n%i==0){

			n=n/i;

			a=i;

			c++;

		}

	}

	}
	
	for(long i=0;i<c;i++){

		if(i!=c-1)

			cout<<a[i]<<" ";

		if(i==c-1)

			cout<<a[i];

	}

}
int main(){

	long n;

	thuasonguyento(n);

	return 0;
}

Kết quả chạy thử vd 2:

Trên đây là toàn bộ cách giải bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++

Mọi vướng mắc trong quá trình giải bài tập bạn đọc comment xuống phía dưới để được hỗ trợ.

Chúc bạn học tập thành công!

LEAVE A REPLY

Please enter your comment!
Please enter your name here