Cấu Trúc Điều Khiển
Vòng Lặp
Hàm - định hướng Số
Đệ Quy
Mảng 1 Chiều
Con Trỏ
Thuật Toán bố trí Và kiếm tìm Kiếm
Mảng 2 Chiều
Chuỗi ký kết Tự
Trong bài học này các bạn sẽ học phương pháp phân tích số nguyên N thành thừa số nguyên tố, đấy là một kỹ năng và kiến thức khó yên cầu bạn cần nắm rõ kiến thức về số nguyên tố trước đó
NỘI DUNG :
Phân Tích vượt Số Nguyên TốCác bài ToánVideo Tutorialmain
1.Phân Tích thừa Số Nguyên Tố
Phân tích quá số thành phần là cách trình diễn số tự nhiên N bên dưới dạng tích những thừa số nguyên tố, cách màn trình diễn này là 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 đúng theo số N cấp thiết đều to hơn √N.
Bạn đang xem: Phân tích ra thừa số nguyên tố là gì
Vì cố kỉnh bạn chỉ việc xét các thừa số thành phần 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 bản thân sẽ gồm giải thích cụ thể hơn.
Thuật toán Trial division :
Duyệt những số d tự 2 cho tới √NNếu N chia hết mang đến d thì thực hiện lấy N phân chia cho d cho tới khi còn phân chia hếtSau lúc duyệt xong các số tự 2 tới √N cơ mà N vẫn không giống 1 thì N chính là thừa 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++) //Neu n chia het cho i, i se la thua kém so nguyen to lớn 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 xích Toán
Bài 1. Phân tích bằng phương pháp thêm vết x giữa những 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 đằng 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 5Bài 2. So với 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^1Bài 3. Liệt kê ước nguyên tố của N
Để liệt mong nguyên tố của N, cách đơn giản và dễ dàng nhất bạn làm là viết 1 hàm số nguyên tố tiếp nối duyệt những ước của N với kiểm tra, nhưng thực ra ước nguyên tố đó 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 một số nguyên các bạn phải nghĩ tức thì tới so với thừa số nguyên tố.
Mình sẽ trình diễn 2 cách, biện pháp 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 buổi 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); int main() prime_divisor(60); return 0;Output :
Để search một mong nguyên tố của số tự nhiên và thoải mái n to hơn 1, ta hoàn toàn có thể làm như sau: Lần lượt có tác dụng phép phân chia n cho các số nhân tố theo thứu từ bỏ tăng dần: 2;3;5;7;11;13;...
Khi đó, phép phân tách hết thứ nhất cho ta số chia là một trong những ước yếu tố của n
II.Phân tích một số ra quá số nguyên tố
- Phân tích một số tự nhiên béo hơn (1) ra vượt số thành phần là viết số đó dưới dạng một tích các thừa số nguyên tố.
- Viết các thừa số nguyên tố theo lắp thêm tự từ bé bỏng đến lớn, tích các thừa số giống như nhau bên dưới dạng lũy thừa. Xem thêm: Câu 1:a) phân tích cấu tạo ngữ pháp là gì, cấu tạo ngữ pháp của câu
Sơ đồ cây:
Bước 1: phân tích số n kết quả của nhì số bất cứ khác 1 và thiết yếu nó.
Bước 2: tiếp tục phân tích ước trước tiên và cầu thứ hai kết quả của hai số bất kì khác 1 và bao gồm nó.
Bước 3: Cứ vậy nên đến bao giờ xuất hiện số nhân tố thì giới hạn lại.
Bước 4: Số n bởi tích của các số ở đầu cuối của mỗi nhánh.
Ví dụ:
Phân tích số 12 ra vượt số nguyên tố bởi sơ đồ vật cây:
Như vậy (12 = 2^2.3)
Sơ trang bị cột:
Chia số (n) cho một số trong những nguyên tố (xét từ nhỏ đến khủng ), rồi phân tách thương kiếm được cho một số trong những nguyên tố (cũng xét từ bé dại đến lớn), cứ liên tiếp như vậy cho tới khi yêu quý bằng (1.)
Ví dụ: Số (76) được so với như sau:
<76> | <2> |
<38> | <2> |
<19> | <19> |
<1> |
|
Như vậy (76 = 2^2.19)
CÁC DẠNG TOÁN VỀ PHÂN TÍCH MỘT SỐ RA THỪA SỐ NGUYÊN TỐ
I. Phân tích những số mang lại trước ra vượt số nguyên tốPhương pháp:
Ta thường phân tích một số trong những tự nhiên $nleft( n > 1 ight)$ ra quá số nguyên tố bởi 2 cách:
+ Sơ đồ vật cây
+ đối chiếu theo mặt hàng dọc.
II. Ứng dụng phân tích một số trong những ra vượt số nguyên tố nhằm tìm những ước của số đóPhương pháp:
+ so với số mang lại trước ra quá số nguyên tố.
+ chăm chú rằng trường hợp $c = a.b$ thì $a$ và $b$ là hai mong của $c.$
$a = b.q$( Leftrightarrow a vdots b Leftrightarrow a in Bleft( b ight)) và (b in )Ư(left( a ight)) $(a,b,q in N,b e 0)$
III. Bài bác toán đem về việc phân tích một số trong những ra thừa số nguyên tố
Phương pháp:
Phân tích đề bài, gửi về việc tìm và đào bới ước của một trong những cho trước bằng phương pháp phân tích số đó ra thừa số nguyên tố.
