Số nguyên tố là gì ? Hàm tìm số nguyên tố

0
412

Tìm Số nguyên tố là một bài toán kinh điển trong lập trình. Vậy số nguyên tố là gì ?  Thường số nguyên tố sẽ được định nghĩa như sau; số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước số là 1 và chính nó.

Có nhiều cách tìm số nguyên tố. Chúng ta cùng làm rõ vấn đề này với oktot nhé.

Ví dụ 1: Viết chương trình kiểm tra số nguyên nhập vào từ bàn phím có phải là số nguyên tố hay không?

Thuật toán:

Đếm số ước của n.
So sánh số ước của n với 2. Nếu số ước bằng 2 thì đó là số nguyên tố, ngược lại không phải số nguyên tố

Code C/C++

Ví dụ 2: Viết chương trình tìm số nguyên tố nhỏ hơn N

Code C/C++

Ví dụ 3: Viết Hàm tìm số nguyên tố

  1. Input: 01 số nguyên dương n (kiểu int)
  2. Output: có hoặc không, đúng hoặc sai, true hoặc false => kiểu trả về là int (1: đúng, 0: sai)
  3. Thuật toán:

    Kiểm tra trong khoảng từ 2 đến n -1. nếu n chia hết một số bất kỳ nào đó thì h không phải là số nguyên tố, ngược lại n là số nguyên tố.

Code C/C++

Cách 1:

Cách 2:

Xem thêm Nhập xuất mảng một chiều

LEAVE A REPLY