viết chương trình kiểm tra số nguyên tố trong c

Thuật toán đánh giá số yếu tắc - Nguyễn Văn Hiếu Blog

Phát biểu câu hỏi đánh giá số nguyên vẹn tố: Cho một trong những nguyên vẹn x nhập kể từ keyboard. Hãy đánh giá coi số x sở hữu cần số yếu tắc hoặc không? Hãy nằm trong blog Nguyễn Văn Hiếu đi kiếm đáp án nhé.

Bạn đang xem: viết chương trình kiểm tra số nguyên tố trong c

Khái niệm số nguyên vẹn tố

Số yếu tắc là số nguyên vẹn dương sở hữu có một không hai 2 ước phân biệt là 1 trong những và chủ yếu nó. Lưu ý: Số 1 ko cần số yếu tắc tự chỉ có một ước.

Thuật toán đánh giá số yếu tắc - Nguyễn Văn Hiếu Blog

  1. Nếu số ê bé nhiều hơn 2, Kết luận ko cần số yếu tắc.
  2. Đếm số ước của x trong khúc kể từ 2 cho tới căn bậc nhì của x. Nếu số ê không tồn tại ước nào là trong khúc từ 2 cho tới căn bậc nhì của x thì nó là số yếu tắc. trái lại thì ko cần. Như vậy, nếu khách hàng điểm từ một thay cho 2 thì x là số yếu tắc Khi tớ điểm được một ước số trong khúc từ một đến căn bậc nhì của x.

Tại sao lại chỉ điểm những ước trong khúc kể từ 2 cho tới căn của x?

Nếu các bạn nhằm ý thì một trong những nguyên vẹn >= 2 ngẫu nhiên tiếp tục luôn luôn sở hữu số ước ở nửa đầu căn bậc 2 của chính nó ngay số ước ở nửa sau căn bậc 2 của chính nó. Cụ thể, những ước tiếp tục phân bổ trở nên 2 miền kể từ [2; sqrt(x)] và kể từ [sqrt(x); x].

Chú ý: Khi đánh giá các bạn ghi nhớ cần là <= sqrt(n) nhé. Nếu chỉ nhằm vết nhỏ hơn vậy thì những số chủ yếu phương như 4, 9 được xem là số yếu tắc đấy. Tại sao thì các bạn demo lý giải coi nào là.

Xem thêm: cường độ dòng điện là gì

for(int i = 2; i <= sqrt(n); i++)

Ví dụ minh họa

Với số 12. tớ sở hữu sqrt(12) xấp xỉ tự 3.464
Đoạn [1; 3.464] sở hữu ước 1, ứng đoạn [3.464; 12] sở hữu ước 12 // 1 * 12 = 12
Đoạn [1; 3.464] sở hữu ước 2, ứng đoạn [3.464; 12] sở hữu ước 6  // 2 * 6 = 12 
Đoạn [1; 3.464] sở hữu ước 3, ứng đoạn [3.464; 12] sở hữu ước 4  // 3*4 = 12
Trong đoạn [2; 3.464] số 12 phân tách không còn mang đến 2 số(2,3)
=> 12 ko là số nguyên vẹn tố
 
Với số chín, tớ sở hữu sqrt(9) = 3
Đoạn [1; 3] sở hữu ước 1, ứng đoạn [3; 9] sở hữu ước 9 // 1*9 = 9
Đoạn [1; 3] sở hữu ước 3, ứng đoạn [3; 9] sở hữu ước 3 // 3*3 = 9
Trong đoạn [2; 3] số chín phân tách không còn cho một số(3)
=> 9 ko là số nguyên vẹn tố

Với số 7, tớ sở hữu sqrt(7) xấp xỉ tự 2.646
Trong đoạn kể từ [2;2.646] không tồn tại số nguyên vẹn nào là tuy nhiên 7 phân tách hết
=> 7 là số yếu tắc.

Dành mang đến bạn: Tự học tập thiết kế Winform C# qua quýt 10 phần mềm thực tế

Code minh họa thuật toán đánh giá số nguyên vẹn tố

Sau phía trên bản thân tiếp tục tổ chức thực hiện code minh họa dùng C/C++, Java và Python mang đến chúng ta. Các chúng ta nên tự động demo trước lúc coi lời nói giải. Không nên copy code =))

Kiểm tra số yếu tắc dùng C

Xem thêm: dục vọng là gì

// Code from https://angiangtourism.net

#include <stdio.h>
#include <math.h>

int main(){
    int n;
    printf("\nNhap n = ");
    scanf("%d", &n);
    if(n < 2){
        printf("\n%d khong nhạt so sánh nguyen to", n);
        return 0;
    }
    int count = 0;
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            count++;
        }
    }
    if(count == 0){
        printf("\n%d la so sánh nguyen to", n);
    }else{
        printf("\n%d khong nhạt so sánh nguyen to", n);
    }
}

Kiểm tra số yếu tắc dùng C++

// Code from https://angiangtourism.net

#include <iostream>
#include <math.h>
using namespace std;

int main(){
    int n;
    cout << "\nNhap n = ";
    cin >> n;
    if(n < 2){
        cout << n << " khong nhạt so sánh nguyen to\n";
        return 0;
    }
    int count = 0;
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            count++;
        }
    }
    if(count == 0){
        cout << n << " la so sánh nguyen to\n";
    }else{
        cout << n << " khong nhạt so sánh nguyen to\n";
    }
}

Kiểm tra số yếu tắc dùng Java

// Code from https://angiangtourism.net 

public class PrimeNumbers {

   public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
       System.out.print("Enter a number : ");
       int n = s.nextInt();
       if (isPrime(n)) {
           System.out.println(n + " is a prime number");
       } else {
           System.out.println(n + " is not a prime number");
       }
   }

   public static boolean isPrime(int n) {
       if (n <= 1) {
           return false;
       }
       for (int i = 2; i <= Math.sqrt(n); i++) {
           if (n % i == 0) {
               return false;
           }
       }
       return true;
   }
}

Nếu các bạn đang được học tập cấu tạo tài liệu và giải thuật, hãy coi tức thì series những thuật toán chuẩn bị xếp sẽ mang lại lợi ích cho chính mình đấy.

Tác giả

Bình luận