Số nguyên tố là số chia hết cho 1 và chính nó. VD: 2, 3 5, 7, 11.. là số nguyên tố.
Như vậy, 2 là số nguyên tố nhỏ nhất.
Vậy, nếu muốn kiểm tra n có phải số nguyên tố hay không, ta kiểm tra n có chia hết cho số nào từ 2 đến n-1 hay không.
Tuy nhiên, để giảm thiểu số vòng lặp, chỉ cần kiểm tra n có chia hết cho các số từ 2 đến phần nguyên căn bậc 2 của n, nếu n không chia hết cho số nào trong đó thì n là số nguyên tố (dựa theo tính chất của hợp số: Mọi hợp số đều có ít nhất một ước số nguyên tố không vượt quá căn bậc hai của nó)
Hàm kiểm tra nguyên tố nhận vào một số nguyên n và trả lại kết quả là true (đúng) nếu n là nguyên tố và trả lại false nếu n không là số nguyên tố.
Code C++
bool ngto(int n){
if (n <2) return false; // nếu nhỏ hơn 2 thì không có số ng tố nào cả
for (int i = 2; i <= sqrt(n); i++) if (n % i == 0) return false;
return true; // nhớ là i<=sqrt(n). nếu không có dấu = là sai nhé
} // không có dấu bằng thì ví dụ 9 cũng sẽ là số ng tố
(thuật toán số ng tố này chỉ dành cho người mới học thôi.
Sau này liên quan đến ng tố đa phần phải sàng (thuật toán nâng cao_sàng số ng tố))
Chú ý: Dựa trên hàm kiểm tra nguyên tố, ta có thể tìm các số nguyên tố từ 2 đến n bằng cách cho i chạy từ 2 đến n và gọi hàm kiểm tra nguyên tố với từng giá trị i.
Tuy nhiên, nếu kiểm tra từ 2 đến N có bao nhiêu số nguyên tố, mỗi lần kiểm tra lại gọi hàm kiểm tra số nguyên tố lần nữa, nên nếu N lớn, thuật toán sẽ mất tg. Tìm hiểu thêm thuật toán nâng cao sàng số nguyên tố (trong file thuật toán nâng cao)
Số chính phương là số khai căn được. VD: 9 là số chính phương vì =3.
Vì nó khai căn được, nên ta sẽ kiểm tra bình phương phần nguyên căn N có bằng N hay không.
Code C++:
bool socp(int n){
for (int i = 0; i <= sqrt(n); i++) if (i*i == n) return true;
return false; // i chạy từ 0 nhé, vì 0 cũng là số cp.
} // nếu i=1, thì nó không kt số 0 và bị bỏ
qua giá trị này dẫn đến thiếu trường hợp
(thuật toán này chạy đúng, nhưng quá thời gian nhé)
Hoặc:
bool check(int n) {
return ceil((double)sqrt(n)) == sqrt(n);
}
(thuật toán này chạy đúng, và không quá thời gian nhé_vậy thì chọn thuật toán này)
Hoặc:
bool socp(int n){
return sqrt(n) * sqrt(n) == n;
}
Hoặc
bool scp(int n){
if (sqrt(n)*sqrt(n)==n) return true;
elsereturn false;
}
(2 thuật toán này chạy chưa đúng, có sai số do việc tính căn trả về kiểu số thực, tuy nhiên nếu nhiều trường hợp chạy trong dev C++ vẫn ra kết quả đúng, thì vào phần mềm Themis chấm vẫn bị sai nha)
(nhưng vẫn đưa ra để so sánh)
Số nguyên gọi là số hoàn hảo (hoàn thiện) nếu nó bằng tổng các ước số của nó (trừ chính nó).
VD: 6 là số hoàn hảo vì: 6 có ước là 1,2,3 (trừ chính nó là 6). Và có tổng: 1+2+3=6.
Để tính tổng các ước số của số n, ta cho i chạy từ 1 đến n div 2, nếu n chia hết cho số nào thì ta cộng số đó vào tổng.
Chú ý: Không cần chạy vòng lặp từ 1 đến n-1. Vì trong toán học, một số sẽ không chia hết cho số nào vượt quá n/2 (trừ chính nó).
VD: n=12. à n/2 = 12/2=6. à 12 sẽ chia hết cho 1,2,3,4,6 chứ k chia hết được cho số >6 ví dụ 7,8,9,… trừ chính nó là số 12.
Code C++ theo cách trên :
bool shh(int n){
if (n<2) return false; // số 0 , số âm, không là số hoàn hảo nhé
int s=0; // nên nếu n<2 thì return false
for (int i = 1; i <= n/2; i++) if (n%i==0) s+=i;
if (s==n) return true;
else return false;
}
TUY NHIÊN: Nếu i chạy đến n / 2 với các số to, số vòng lặp sẽ lớn. Ta có thể chạy đến phần nguyên căn n [] sẽ giảm thiểu rất nhiều vòng lặp.
Th1: Nếu n là số khai căn được, thì sẽ có nghiệm bình phương lên bằng n, lúc này ta chỉ cộng 1 lần nghiệm mà thôi, nên có câu lệnh: if sqr(i)=n then s=s+I;
TH2: Nếu n chia hết cho i, thì ta cộng tổng ước với 2 nghiệm là i và n / i: s= s+i+n / i
(trong đó (n / i)*i=n )
VD: n=28: [] = 5. → i:[2..5]
i=2 → s:=s+(i+n / i)= 1+ (2+14) = 17. (2*14=28)
i=4 → s:=s+(i+n / i)= 17+ (4+7) = 28. (4*7=28).
Vậy tại sao lại chạy đến []. Tìm hiểu thêm thuật toán đếm ước bên dưới.
bool shh(int n){
if (n<2) return false;
int s = 1; // s=1 nhé
for(int i = 2; i <= sqrt(n); i++){
if (n % i == 0) s =s + i + n/i;
if (i*i == n) s = s - i;
}
if (s == n) return true;
return false ;
}
Tuy nhiên, thuật toán kiểm tra số hoàn hảo trên sẽ rất chậm nếu n lớn.
Khắc phục:
Để đếm các ước số của số n, ta cho i chạy từ 1 đến n, nếu n chia hết cho i thì ta tăng biến đếm lên 1 đơn vị.
Code c
// ĐẾM SỐ ƯỚC
int demuoc(int n) {
int dem = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) dem += 1;
}
return dem;
}
Tuy nhiên, không nên làm theo cách trên.
Vậy ta làm như sau: nếu chia n thành 2 nửa, lấy [] (phần nguyên căn N) làm mốc, thì chúng ta thấy rằng, trong toán học, nếu n chia hết cho số nào ở bên nửa trái, nó cũng sẽ chia hết cho 1 số bên nửa phải.
N chia hết cho 1 thì bên kia cũng chia hết cho một số là 10.
N chia hết cho 2 thì bên kia cũng chia hết cho một số là 5.
N chia hết cho 1 thì bên kia cũng chia hết cho một số là 9.
N chia hết cho 3 thì 9=3.3 nên bên kia k có số nào nhân với 3=9 nữa.
int demuoc(int n) {
int dem = 0;
for (int i = 1; i <= sqrt(n); i++) {
if (n % i == 0)
dem += 2;
}
if (sqrt(n) == (int)sqrt(n)) // nếu nó là số chính phương
dem--; // thì phải trừ đi 1 ước.
return dem;
}
Ý tưởng của thuật toán Euclide là UCLN của 2 số a,b cũng là UCLN của 2 số b và a mod b, vậy ta sẽ đổi a là b, b là a mod b cho đến khi b bằng 0. Khi đó UCLN là a. Phương pháp chia này trong nhiều trường hợp sẽ nhanh hơn phương pháp trừ dần.
Hàm UCLN nhận vào 2 số nguyên a,b và trả lại kết quả là UCLN của 2 số đó.
|
Thuật toán Euclide (chia) (nên dùng thuật toán này) |
Thuật toán trừ dần |
|
long long gcd (int a, int b) { while (b != 0) { int r = a % b; a = b; b = r; } return a; }
Hoặc: int gcd(int a, int b) { // như thế này cho ngắn gọn if (b == 0) return a; return gcd(b, a % b); } Dùng phương pháp chia dần, chia cho đến khi nào b=0. (nên dùng phương pháp chia thay cho pp trừ dần) Thuật toán Ơclit dựa vào hai mệnh đề sau :
Ví dụ : Tìm (702,306) Ta có : 702 = 301.2 + 90 (702,306) = (306,90) 306 = 90.3 + 36 (306,90) = (90,36) 90 = 36.2 + 18 (90,36) = (36,18) = 18 (702,306) = 18. Minh họa phép chia:
|
int gcd (int a,int b){ while (a!=b) do if (a>b) a=a-b; else b=b-a; return a; } Dựa theo tính chất: a=b thì (a,b) sẽ bằng a hoặc bằng b. Dùng phương pháp trừ dần, trừ cho đến khi nào 2 số bằng nhau thì đó là UCLN: Nếu M>N thì M = M-N ngược lại thì N = M-N.
vd: M=20. N=5. M>N à M= 20-5=15. M vẫn lớn hơn n: M=M-N=15-5=10. M vẫn lớn hơn N: M=M-N=10-5=5.
Lúc này, M=5, N=5 à UCLN của (5,5) là 5.
|
Chú ý: Dựa trên thuật toán tính UCLN ta có thể kiểm tra được 2 số nguyên tố cùng nhau hay không.
Hoặc tìm bội chung nhỏ nhất.
Code C++
long long gcd(int a, int b) { // tim UCLN
if (b == 0) return a;
return gcd(b, a % b);
}
long long lcm (int a,int b){ // tim BCNN
return a*b/ gcd (a,b);
}
// tuy nhiên chỗ này chú ý nhé: a*b/gdc(a,b); nếu kết quả phép nhân a*b, mà quá kiểu dữ liệu long long, thì nên tách ra để đỡ quá nhé:
Tách thành: a*(b/gdc(a,b)); hoặc (a/ gcd (a,b))*b;
Một xâu gọi là palindrom (đx) nếu nó đọc từ trái sang cũng bằng đọc từ phải sang. Ví dụ 121, aba là một xâu palindrom.
Đặc biệt: Xâu có 1 kí tự cũng là xâu đối xứng. xâu rỗng cũng là xâu đối xứng.
C1: Tạo xâu ngược, sau đó so sánh 2 xâu. Nếu bằng nhau thì là đối xứng.
// tạo xâu ngược : chạy vòng for ngược để tạo thành s1 (nhưng chạy vòng for xuôi cũng tạo được nhé_tuy nhiên phải để ý đổi chỉ số)
string s1=””; // tạo xâu rỗng s1
int n=s.size();
for (int i = n-1; i>=0; i--) { // chạy vòng for ngược để tạo thành s1.
s1=s1+s[i]; // Nhớ int i = n-1. Nếu int i = n là chạy sai đấy
}
if (s1==s) cout<<”dx”;
else cout<<”khong dx”;
}
C2: Sử dụng chỉ số để kiểm tra.
Nếu sử dụng cách 1, chương trình đơn giản, nhưng mất tg hơn.
Ta để ý thấy rằng, nếu là xâu đx, thì phần tử đầu s[i]=phần tử cuối s[n-i-1], tương tự, các phần tử khác cũng đối xứng qua tâm của xâu.
Ví dụ: AABBAA
S[0] S[1] S[4] S[5]
S[i] S[n-i-1] = S[6-0-1] = S[5]
Vì vậy, ta có thể chia xâu làm đôi, kt nếu có cặp phần tử nào khác nhau, ta break luôn.
// không dùng hàm
bool kt=true;
int n=s.size();
for (int i = 0; i<=n/2; i++) {
if (s[i] != s[n – i-1])
{
kt=false;
break; }
}
Hoặc tạo thành hàm đối xứng như sau:
// dùng hàm
bool dx(string s) {
int n=s.size();
for (int i = 0; i<=n/2; i++)
if (s[i] != s[n – i - 1]) return false; // nếu có cặp khác nhau thì trả về false
return true; // nếu không có cặp nào khác nhau, tức là xâu dx, nên trả về true.
}
Ý tưởng là ta chia số đó cho 10 lấy dư (%) thì được chữ số hàng đơn vị, và lấy số đó / 10 thì sẽ được phần còn lại. Do đó sẽ chia liên tục cho đến khi không chia được nữa (số đó bằng 0), mỗi lần chia thì được một chữ số và ta cộng dồn chữ số đó vào tổng.
Hàm tính tổng chữ số nhận vào 1 số nguyên n và trả lại kết quả là tổng các chữ số của nó:
// hàm tính tổng chữ số
int tongcs(int n){
int s=0;
while (n!=0){
s=s+n%10;
n=n/10;
}
return s;
}
Chú ý: Dựa vào 1 thuật toán tính tổng, chúng ta có thể hiểu cách tính, để tính được tích, đếm được số chữ số,….
Giai thừa n! là tích các số từ 1 đến n. Vậy hàm giai thừa viết như sau:
Trong Pascal ta có thể tính ab bằng công thức exp(b*ln(a)). Tuy nhiên nếu a không phải là số dương thì không thể áp dụng được.
Ta có thể tính hàm mũ an bằng công thức lặp như sau: