Viết chương trình phân tích một số ra thừa số nguyên tố

Ví dụ: Phân tích 12=2*2*3. Ý tưởng: Thuật toán phân tích một số ra thừa số nguyên tố tương tự như thuật toán kiểm tra số nguyên tố. Điểm khác ở đây là khi kiểm tra số nguyên tố ta phải lần lượt kiểm tra các số nhỏ hơn sqrt(n) (căn bậc hai của n) có phải là ước của n hay không, còn khi phân tích ta chỉ việc chia n cho các số nguyên bắt đầu từ số nguyên tố nhỏ nhất là 2. Khi không chia được nữa thì ta tăng số chia lên 1 đơn vị, quá trình phân tích kết thúc khi n bằng 1.

VAR i,n :INTEGER;
BEGIN
    Write ('Nhap n:');
    Readln(n);
    Write (n,'=');
    i:=2;
    REPEAT
        WHILE n MOD i <> 0 DO
            i:=i+1;
        Write(i);
        n:=n DIV i;
        IF n > 1 THEN
            write ('*');
    UNTIL n = 1;
    readln;
END.

60 điểm

NguyenChiHieu

Viết chương trình cho phép phân tích một số ra thừa số nguyên tố và ghi kết quả dưới dạng tích các lũy thừ
a. Ví dụ: 300 = 2^2.3.5^2

Tổng hợp câu trả lời (1)

Program Phan_tich; Var M: array[1..1000] of byte; i: byte; n: integer; Begin For i:=1 to 1000 do M[i]:=0; Write('Nhap so n: ');Readln(n); i:=2; While n>1 do if (n mod i = 0) then begin M[i]:=M[i]+1; n:=n div i End else i:=i+1; For i:=1 to 1000 do if M[i]>0 then Begin If M[i]>1 then Write(i,'^',M[i],'.') else Write(i,'.') End; Readln; End.

Câu hỏi hay nhất cùng chủ đề

• Viết chương trình cho phép sắp xếp một dãy số với yêu cầu sử dụng các chương trình con: Nhập mảng, in mảng, đổi giá trị của hai số.
• Phát biểu nào dưới đây chắc chắn sai? A. Lập trình là viết chương trình B. Lập trình và chương trình là hai khái niệm tương đương, đều là cách mô tả thuật toán bằng ngôn ngữ lập trình C. Chương trình được tạo thành từ tổ hợp các câu lệnh và các khai báo cần thiết về biến, hằng, hàm, … D. Chương trình chưa chắc là đã đúng nếu cho kết quả đúng với rất nhiều bộ dữ liệu vào.
• Viết chương trình cho phép thực hiện rút gọn phân số.
• Để thực hiện gán giá trị 10 cho biến X. Phép gán nào sau đây là đúng ? A. X = 10; B. X := 10; C. X =: 10; D. X : = 10;
• Khai báo nào sau đây đúng? A. Var x, y: Integer; B. Var x, y=Integer; C. Var x, y Of Integer; D. Var x, y := Integer;
• Trong ngôn ngữ lập trình Pascal, câu lệnh nào sau đây là khai báo hằng? A. Const max = 50; B. Const max := 50; C. Const integer max = 50; D. Const max 50;
• Cho x, y, z là ba biến nguyên. Cách nhập giá trị nào sau đây là sai khi muốn nhập giá trị 3, 4, 5 cho ba biến này từ bàn phím bằng câu lệnh readln(x,y,z); ? A. Gõ 3, 4, 5 sau đó nhấn phím Enter (giữa hai số liên tiếp gõ dấu phẩy); B. Gõ 3, 4, 5 sau đó nhấn phím Enter (giữa hai số liên tiếp gõ một dấu cách); C. Gõ 3 sau đó nhấn phím Enter rồi gõ 4 sau đó nhấn phím Enter rồi gõ 5 sau đó nhấn phím Enter; D. Gõ 3 sau đó nhấn phím Tab rồi gõ 4 sau đó nhấn phím Tab rồi gõ 5 sau đó nhấn phím Enter;
• Trong ngôn ngữ lập trình Pascal, biểu thức số học nào sau đây là hợp lệ ? A. 5a + 7b + 8c; B. 5*a + 7*b + 8*c; (*) C. {a + b}*c; D. X*y(x+y);
• Trong ngôn ngữ lập trình Pascal, với câu lệnh như sau (a là một biến kiểu số thực): a :=2345 ; Writeln('a = ', a:8:3); Sẽ ghi ra màn hình? A. a = 2.345 B. a = 2.345E+01 C. Không đưa ra gì cả D. a = 2345.000
• Phát biểu nào dưới đây là hợp lí nhất A. Biến dùng trong chương trình phải khai báo B. Biến được chương trình dịch bỏ qua C. Biến có thể lưu trữ nhiều loại giá trị khác nhau D. Biến là đại lượng nhận giá trị trước khi chương trình thực hiện

Tham khảo giải bài tập hay nhất

Loạt bài Lớp 11 hay nhất

xem thêm

Đề bài: Nhận 1 số nguyên n từ bàn phím, sau đó phân tích số nguyên dương n ra các thừa số nguyên tố. Yêu cầu viết hàm phân tích số nguyên n ra thừa số nguyên tố bằng kỹ thuật chương trình con. Tên hàm là phanTichThuaSoNguyenTo. Ví dụ:

• 18 = 2 3 3 
• 32 = 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
• 33 = 3 11

(ở đây các số 2,3, 11 đều là số nguyên tố - xem bài kiểm tra 1 số có là số nguyên tố hay không?)

Bài giải:

#include

void phanTichThuaSoNguyenTo(int n){ i = 2;
while (n>1){
if (n%i==0){
printf("%d ",i);
n=n/i;
}
else{
i
int main(){
int n;
printf("nhap so n: ");
scanf("%d",&n);
printf("%d = ",n); phanTichThuaSoNguyenTo(n); 0;
}
Xem Video: Phan tich so nguyen n ra thua so nguyen to

Đề bài: Phân tích một số thành tích các thừa số nguyên tố

Với bài này các bạn cần nhớ lại thừa số nguyên tố là gì và cách phân tích một số ra thừa số nguyên tố.

Tích các thừa số nguyên tố chính là phép nhân giữa các số với nhau trong đó tất cả các số đều là số nguyên tố. Ví dụ: 10 = 2 * 5. Trong đó 2 và 5 là các số nguyên tố.

18 = 2 * 3 * 3. Trong đó 2 và 3 là các số nguyên tố.

Cách phân tích ra thừa số nguyên tố:
Ở các lớp cấp 1 và 2 gì đó mình không nhớ rõ, chúng ta đã được học rồi. Chúng ta sẽ thực hiện các phép chia liên tiếp số cần phân tích cho các số nguyên tố đến khi nào thương là 1 thì dừng lại. Ví dụ phân tích số 140.

140 | 2 70 | 2 35 | 5 7 | 7 1

Chúng ta lấy 140 chia 2 (2 là số nguyên tố) được 70. Thấy 70 vẫn chia được cho 2 nên ta chia tiếp được 35. Thấy 35 không chia hết cho 2 nữa, số nguyên tố tiếp theo là 3 cũng không chia hết mà chia hết cho 5 nên ta chia cho 5 được 7. Đến đây 7 chia 7 được 1. Thương là 1 nên ta dừng lại. Vậy 140 = 2 * 2 * 5 * 7

Vậy là chúng ta đã nhớ lại cách làm. Tổng kết lại là chúng ta lấy số đó chia cho các số nguyên tố nhưng có thể lặp lại. Trong khi vẫn chia hết cho số 2 thì cứ chia đến khi nào không chia được thì tìm số khác để chia và cũng làm như vậy.

Nhưng làm sao để biết được các số nguyên tố nào sẽ được dùng để chia? Với các số bé như các ví dụ này chúng ta có thể nhẩm nhanh được, nhưng với các số lớn hơn thì chúng ta khó nhẩm được và cũng không phải là số nguyên tố nào cũng có thể dùng, ví dụ như số 140 chúng ta không có dùng đến số 3 dù số 3 là số nguyên tố. Đơn giản là chúng ta chọn những số mà thương hiện tại của chúng ta có thể chia hết bằng cách dùng vòng lặp để duyệt và kiểm tra hết các số từ 2 đến n (n là số cần phân tích). Vậy giờ thử code theo hướng mà chúng ta đã suy nghĩ xem sao.

/** * Nhap vao 1 so tu nhien va phan tich ra thua so nguyen to */ #include #include int isPrime(int n) { int i; int m = (int) sqrt(n); for (i = 2; i <= m; i++) { if(n % i == 0) return 0; } return 1; } int main() { int n, i; printf("Enter number n = "); scanf("%d", &n); printf("%d = ", n); for (i = 2; i <= n; i++) { while( isPrime(i) && (n % i == 0) ) { printf("%d.", i); n = n / i; } } return 0; }

Như code trên các bạn thấy chúng ta đã làm theo đúng như các bước trên. Lưu ý là có 1 hàm để kiểm tra số nguyên tố nhé.

Tuy nhiên thì code bên trên có thể rút gọn đi rất nhiều. Các bạn thử suy nghĩ một chút trước khi đọc tiếp nhé.

Các bạn để ý là khi chúng ta đã chia 140 cho 2 đến khi không thể chia cho 2 được nữa thì chắc chắn nó không chia hết cho 4, 6, 8… vì nếu chia hết cho 4,6,8… thì chắc chắn nó chia hết cho 2. Tương tự khi kiểm tra đã khồn còn có thể chia hết cho 3 thì sẽ không thể chia hết cho 6,9,12… Từ đó ta nhận thấy là các số phía sau thì n không bao giờ chia hết nếu nó là bội của các số đã kiểm tra mà chỉ có thể chia hết cho các số chưa kiểm tra, mà các số chưa kiểm tra đó chính là các số nguyên tố. Do vậy chúng ta sẽ không cần kiểm tra các số có là số nguyên tố hay không. Code của chúng ta sẽ gọn hơn rất nhiều mà kết quả không hề sai.

/** * Nhap vao 1 so tu nhien va phan tich ra thua so nguyen to */ #include #include int main() { int n, i; printf("Enter number n = "); scanf("%d", &n); printf("%d = ", n); for (i = 2; i <= n; i++) { while(n % i == 0) { printf("%d.", i); n /= i; } } return 0; }

Rất đơn giản phải không! ^^. Nếu bạn nào để ý thì thuật toán này dựa trên thuật toán sàng nguyên tố.