KIỂM TRA SỐ NGUYÊN TỐ TRONG C

     

Trong bài bác này mình sẽ trình bày thuật toán nhằm kiểm tra một vài có yêu cầu là số nguyên tố tốt không, sau khoản thời gian giới thiệu hoàn thành thuật toán mình đang sử dụng ngôn từ C++ để giải mẫu cho những bạn. Trước tiên chúng ta tìm hiểu quan niệm số yếu tố là gì sẽ nhé.

Bạn đang xem: Kiểm tra số nguyên tố trong c

*


*

1. Số thành phần là gì?

Theo tư tưởng của Wikipedia thì số nguyên tố là số trường đoản cú nhiên lớn hơn 1, chỉ có 2 ước là một trong và thiết yếu nó. Theo quan niệm này thì những số 2, 3, 5, 7, 11, ... Là những số nguyên tố, trong các số ấy số 2 là số nhân tố chẵn duy nhất. Cũng tương tự tính chất của số nguyên dương, bọn họ chỉ tra cứu thấy số nguyên tố bé dại nhất chứ không thể tìm thấy số nguyên tố lớn nhất.

Ví dụ: 7 là số nguyên tố vì trong khoảng từ 2 - 6 ko tồn tại số nào cơ mà 7 phân tách hết cả.

Xem thêm: Ý Nghĩa Chú Cuội Và Chị Hằng Nga, Sự Tích Về Chi Hằng Nga Và Chú Cuội Cung Trăng

2. Thuật toán kiểm soát số nguyên tố

Dựa vào quan niệm của số nguyên tố họ sẽ có một số trong những cách giải như sau (các lấy một ví dụ được viết bằng ngữ điệu C++):

Bài viết này được đăng tại

Cách 1: Lặp từng bộ phận với cách nhảy 1

Giả sử đề nghị kiểm tra số n liệu có phải là số nguyên tố hay là không thì công việc thực hiện nay như sau:

Bước 1: Nhập vào nBước 2: bình chọn nếu n thì kết luận n chưa phải là số nguyên tốBước 3: Lặp từ bỏ 2 tới (n-1), nếu trong khoảng này tồn tại số nhưng n phân tách hết thì tóm lại n chưa phải là số nguyên tố, trái lại n là số nguyên tố.


bool laSoNguyenTo1(int n){// Neu n

Hàm main:


void main(){int n;cout > n;if (laSoNguyenTo1(n)){cout

Cách 2: Lặp từng phần tử với cách nhảy 2

Theo có mang thì số 2 là số yếu tắc chẵn duy nhất, vì chưng vậy ta sẽ nhiều loại 2 thoát khỏi vòng lặp và trong thân vòng lặp chỉ kiểm tra các số lẻ nhưng mà thôi, bí quyết này sẽ buổi tối ưu hơn phương pháp 1 khôn cùng nhiều.

Xem thêm: Đề Kiểm Tra 1 Tiết Vật Lý 9 Chương 1 Violet, Đề Kiểm Tra 1 Tiết Hóa 9 Chương 3 Violet


bool laSoNguyenTo2(int n){// Neu n

Hàm main:


void main(){int n;cout > n;if (laSoNguyenTo2(n)){cout

3. Lời kết

Vẫn còn rất nhiều cách khác nhưng bình thường quy lại vẫn phải bám vào định nghĩa số yếu tắc là gì. Ví dụ trong khoảng lặp điểm dừng sẽ là (n/2) thay vị (n-1) vì theo kim chỉ nan thì một vài không lúc nào chia hết mang đến số một ít của nó. Ví dụ như số 9 thì số một nửa của nó là số (9 : 2 = 4), vậy nên ta chỉ việc kiểm tra các số từ 2,3,4 cơ mà thôi, còn những số 5,6,7,8 cứng cáp chẵn 9 sẽ không chia hết.