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 Việc đánh giá số vẹn toàn tố: Cho một trong những vẹn toà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 tìm 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ố vẹn toàn tố

Số yếu tắc là số vẹn toà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ại bé thêm hơn 2, Tóm lại 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ố bại 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 như khách hàng kiểm điểm từ là 1 thay cho 2 thì x là số yếu tắc Lúc tao kiểm điểm được một ước số trong khúc từ là 1 đến căn bậc nhị của x.

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

Nếu chúng ta nhằm ý thì một trong những vẹn toà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á chúng ta lưu giữ cần là <= sqrt(n) nhé. Nếu chỉ nhằm lốt nhỏ hơn thế 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ì chúng ta demo phân tích và lý giải coi nào là.

Xem thêm: số mặt phẳng đối xứng của khối tứ diện đều

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

Ví dụ minh họa

Với số 12. tao sở hữu sqrt(12) xấp xỉ vày 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 chia không còn mang lại 2 số(2,3)
=> 12 ko là số vẹn toàn tố
 
Với số cửu, tao 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ố cửu phân chia không còn cho một số(3)
=> 9 ko là số vẹn toàn tố

Với số 7, tao sở hữu sqrt(7) xấp xỉ vày 2.646
Trong đoạn kể từ [2;2.646] không tồn tại số vẹn toàn nào là nhưng mà 7 phân chia hết
=> 7 là số yếu tắc.

Dành mang lại bạn: Tự học tập xây dựng Winform C# qua loa 10 phần mềm thực tế

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

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

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

Xem thêm: trình bày đặc điểm cấu tạo ngoài của thằn lằn thích nghi với đời sống hoàn toàn ở cạn

// Code from https://tamkyrt.com

#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 ví 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 ví nguyen to", n);
    }else{
        printf("\n%d khong nhạt ví nguyen to", n);
    }
}

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

// Code from https://tamkyrt.com

#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 ví 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 ví nguyen to\n";
    }else{
        cout << n << " khong nhạt ví nguyen to\n";
    }
}

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

// Code from https://tamkyrt.com 

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 chúng ta đang được học tập cấu tạo tài liệu và giải thuật, hãy coi ngay lập tức 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