Bài 11.3 KIỂM TRA SỐ NGUYÊN TỐ VER 3

Xem ra có vẻ thuật toán của chúng ta đã tạm ổn, và chương trình đã chạy tương đối nhanh! Tuy nhiên, như
đã phân tích từ đầu, số nguyên tố là các số lẻ, trừ số 2. Vì thế chúng ta chỉ cần kiểm tra các ước số của N là các
số lẻ, nếu chúng không phải là ước số của N thì N chính là nguyên tố, ngược lại, là hợp số. Thuật toán 3 được cải
tiến thành thuật toán 4, như sau:

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

     bool check_prime (const int n) {
    // 2 is prime
    if (n == 2)
        return true;
    // 1 is not a prime
    // each even number is not a prime
    if (n == 1 || n % 2 == 0)
        return false;
    // if we’ll find any divisor of n, then n is a combine
    // you should save the value of sqrtl(n) in a temporary
    // variable, otherwise program will calculate sqrt and
    // call function sqrtl, it will take a long time ...
    int j = sqrt (  n ) ;
    for (int i = 3; i <= j; i +=  2)
        if (n % i == 0)
            return false;
    // in the end, n is a prime
    return true;
}

main ( )
{
     int n ;
     char ktra ;
   do{
     printf ( " n = ") ;
     scanf("%d", &n ) ;
  if (check_prime ( n )== true )
  printf ("%d nguyen to .\n", n ) ;
  else
  printf ("%d khong nguyen to.\n", n ) ;
     printf ("Tiep ? (an chu c neu khong an chu khac ):") ;
     ktra = getche();
     printf("\n\n");                
  }while ( ktra == 'c' ) ;
     getch();
     }