Kiểm tra SNT

1. Cách làm "ngây thơ"?:
   
   C++

   bool is_prime_SLOW(int n) {
       if (n < 2) return false;
       for (int i = 2; i < n; i++)
           if (n%i == 0) return false; // n có ước khác 2 và chính nó
       return true;
   }
   

   
   Trong Python:
   
   Python

   def check_prime(n):
       if n < 2: return False
       for i in range(2,n):
           if n % i == 0: return False
       return True
   

2. Cách làm tối ưu: Ta chỉ sửa giới hạn của vòng lặp for
   Điểm khác biệt là:
   
   C++

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

   
   Hoặc:
   
   Python

       for i in range(2, n**0.5 + 1):
   

   
   Code hoàn chỉnh như sau:
   
   C++

   bool is_prime(long long n) {
       if (n < 2) return false;
       for (int i = 2; i <= n/i; i++)
           if (n%i == 0) return false;
       return true;
   }
   

   
   Hoặc:
   
   Python

   def is_prime(n):
       if n < 2: return False
       for i in range(2, n**0.5 + 1):
           if n % i == 0: return False
       return True