LATEST

Kiểm tra số nguyên tố trong C / C++

Trong bài viết này, codehow sẽ hướng dẫn các bạn cách kiểm tra số nguyên tố trong C / C++. Dựa vào đó ta có thể thực hiện thêm chương trình in các số nguyên tố trong một phạm vi nhất định.

Trước khi đi vào viết chương trình, ta cùng tìm hiểu qua số nguyên tố là gì? Cách nhận biết số nguyên tố đã nhé.

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Nghĩa là không có tích của hai số tự nhiên bất kỳ nào bằng nó cả.

Ví dụ 1: Ta có số 5 là số nguyên tố, bởi vì 5 chia chỉ hết cho 1 và 5 mà thôi.

Ví dụ 2: Ta có số 6 không phải là số nguyên tố, bởi vì 6 chia hết cho 1, 2, 3, 6.

Qua ví dụ trên chắc các bạn cũng đã hiểu sơ qua về số nguyên tố rồi đúng không ạ. Bây giờ chúng ta sẽ cùng nhau viết chương trình kiểm tra số nguyên tố trong C / C++ thôi nhé!!!

Kiểm tra số nguyên tố trong C / C++

Trước khi đi vào viết chương trình, chúng ta hãy cùng tìm hiểu qua thuật toán kiểm tra số nguyên tố trong C / C++ đã nhé.

bool laSoNguyenTo(int n)
{
    if (n < 2){
        return false;
    }       
    for (int i = 2; i < (n - 1); i++){
        if (n % i == 0){
            return false;
        }   
    }
    return true;
}

Như các bạn đã thấy ở đoạn chương trình trên. Nếu n < 2 thì đây không phải la số nguyên tố. Sau đó sử dụng vòng lặp từ 2 đến n - 1, nếu trong khoảng này tồn tại một số mà n chia hết thì đó không phải là số nguyên tố. Ngược lại số mà n không chia hết sẽ là số nguyên tố.

Ngoài ra, các bạn cũng có thể kiểm tra số nguyên tố theo cách dưới đây:

bool laSoNguyenTo(int n)
{
    if (n < 2){
        return false;
    }       
    if (n == 2){
        return true;
    }
    if (n % 2 == 0){
        return false;   
    }
    for (int i = 3; i < (n - 1); i += 2){
        if (n % i == 0){
            return false;
        }   
    }
    return true;
}

Ví dụ: Kiểm tra số nguyên tố trong C / C++.

Chương trình C:

#include <stdio.h>
#include <stdbool.h>
bool laSoNguyenTo(int);

int main(void) {
 int n;
  do{
    printf("Nhập vào một số: ");
    scanf("%d", &n);
    if(n < 2) printf("Nhập vào số lớn hơn 2!!\n");
  }while(n < 2);
    if(laSoNguyenTo(n)){
      printf("%d là số nguyên tố!",n);
    }
  else{
    printf("%d không là số nguyên tố!",n);
  }
  
  printf("\n----------------------------\n");
  printf("chương trình này được đăng tại codehow.net");
}

bool laSoNguyenTo(int n)
{
    if (n < 2){
        return false;
    }       
    for (int i = 2; i < (n - 1); i++){
        if (n % i == 0){
            return false;
        }   
    }
    return true;
}

Kết quả:

bai6 01 PNG

Chương trình C++:

#include <iostream>
using namespace std;

bool laSoNguyenTo(int);

int main()
{
    int n;
  do{
    cout<<"Nhập vào một số: ";
    cin>>n;
    if(n < 2) cout<<"Nhập vào số lớn hơn 2!!\n";
  }while(n < 2);
    if(laSoNguyenTo(n)){
      cout<<n<<" là số nguyên tố!";
    }
  else{
    cout<<n<<" không là số nguyên tố!";
  }
    
    cout<<"\n----------------------------\n";
    cout<<"chương trình này được đăng tại codehow.net";
}

bool laSoNguyenTo(int n)
{
    if (n < 2){
        return false;
    }       
    for (int i = 2; i < (n - 1); i++){
        if (n % i == 0){
            return false;
        }   
    }
    return true;
}

Kết quả:

bai6 02 PNG

In các số nguyên tố trong phạm vi nhất định

Dựa vào thuật toán kiểm tra số nguyên tố trong C / C++, bây giờ chúng ta sẽ thực hiện một chương trình phức tạp hơn một tý như sau:

  • Yêu cầu người dùng nhập vào một số lớn hơn 1, nếu nhỏ hơn 1 thì yêu cầu nhập lại.
  • In các số nguyên tố trong phạm vi từ 1 đến số được nhập bởi người dùng.

Chương trình C:

#include <stdio.h>

int main(void) {
 int num1, num2, flag_var, i, j;
  printf("Nhập vào số bắt đầu: ");
  scanf("%d", &num1);
  printf("Nhập vào số kết thúc: ");
  scanf("%d", &num2);
   printf("Các số nguyên tố từ %d đến %d là: \n",num1,num2);
   for(i=num1+1; i<num2; ++i)
   {
      flag_var=0;
      for(j=2; j<=i/2; ++j)
      {
         if(i%j==0)
         {
            flag_var=1;
            break;
         }
      }
      if(flag_var==0)
         printf("%d\n",i);
  }
  
  printf("\n----------------------------\n");
  printf("chương trình này được đăng tại codehow.net");
}

Chương trình C++

#include <iostream>
using namespace std;
int main()
{
  int num1, num2, flag_var, i, j;
  cout<<"Nhập vào số bắt đầu: ";
  cin>>num1;
  cout<<"Nhập vào số kết thúc: ";
  cin>>num2;
   cout<<"Các số nguyên tố từ "<<num1<<" đến "<<num2<<" là: \n";
   for(i=num1+1; i<num2; ++i)
   {
      flag_var=0;
      for(j=2; j<=i/2; ++j)
      {
         if(i%j==0)
         {
            flag_var=1;
            break;
         }
      }
      if(flag_var==0)
         cout<<i<<endl;
  }
  cout<<"\n---------------------------------\n";
  cout<<"Chương trình này được đăng tại codehow.net";
}

Kết quả:

bai6 03 PNG

Như vậy là chúng ta đã cùng nhau tìm hiểu về cách kiểm tra số nguyên tố trong C / C++, cũng như cách in các số nguyên tố trong một phạm vi nhất định. Hãy xem nhiều bài tập hơn tại serries bài tập C / C++ codehow nhé, cảm ơn các bạn rất nhiều !!!

Cùng chuyên mục:

Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Danh sách liên kết (Linked List) là gì? Các loại danh sách liên kết

Sử dụng đệ quy để giải bài toán tháp Hà Nội

Sử dụng đệ quy để giải bài toán tháp Hà Nội

Đệ quy tương hỗ (Mutual Recursion) trong C / C++

Đệ quy tương hỗ (Mutual Recursion) trong C / C++

Đệ quy lồng (Nested Recursion) trong C / C++

Đệ quy lồng (Nested Recursion) trong C / C++

Đệ quy đa tuyến (Exponential Recursion) trong C / C++

Đệ quy đa tuyến (Exponential Recursion) trong C / C++

Đệ quy nhị phân (Binary Recursion) trong C / C++

Đệ quy nhị phân (Binary Recursion) trong C / C++

Đệ quy đuôi (Tail Recursion) trong C / C++

Đệ quy đuôi (Tail Recursion) trong C / C++

Đệ quy tuyến tính (Linear Recursion) trong C / C++

Đệ quy tuyến tính (Linear Recursion) trong C / C++

Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Hàm đệ quy là gì? Các loại hàm đệ quy trong C / C++

Thuật toán sắp xếp Quick Sort trong C / C++

Thuật toán sắp xếp Quick Sort trong C / C++

Thuật toán sắp xếp trộn (Merge Sort) trong C / C++

Thuật toán sắp xếp trộn (Merge Sort) trong C / C++

Thuật toán sắp xếp chọn (Selection Sort) trong C / C++

Thuật toán sắp xếp chọn (Selection Sort) trong C / C++

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Thuật toán sắp xếp chèn (Insertion Sort) trong C / C++

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Thuật toán sắp xếp nổi bọt (Bubble Sort) trong C / C++

Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++

Thuật toán tìm kiếm nội suy (Interpolation Search) trong C / C++

Thuật toán tìm kiếm nhị phần (Binary Search) trong C / C++

Thuật toán tìm kiếm nhị phần (Binary Search) trong C / C++

Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++

Thuật toán tìm kiếm tuyến tính (Linear Search) trong C / C++

Thuật toán kiểm tra năm nhuận trong C / C++

Thuật toán kiểm tra năm nhuận trong C / C++

Thuật toán kiểm tra số chẵn lẻ trong C / C++

Thuật toán kiểm tra số chẵn lẻ trong C / C++

Thuật toán tính lũy thừa trong C / C++

Thuật toán tính lũy thừa trong C / C++

Top