Advertisement
huutho_96

Tổng n số nguyên tố đầu tiên - Đệ quy

Nov 22nd, 2016
299
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <iostream>
  2. #include<math.h>
  3.  
  4. using namespace std;
  5.  
  6. // hàm kiểm tra số nguyên tố
  7. bool snt(int n)
  8. {
  9.     // tính căn bậc 2 của n
  10.     int sqrt_n = sqrt(n);
  11.     // nếu n < 2 return false
  12.     if (n < 2) return false;
  13.     // i chạy từ 2 đến căn bậc 2 của n, chỉ cần n % i bằng 0 với i bất kì thì đây không phải số nguyên tố => false
  14.     for (int i = 2; i <= sqrt_n; i++)
  15.     {
  16.         if (n % i == 0)
  17.             return false;
  18.     }
  19.     // nếu chạy được tới đây tức là không có i nào để n % i bằng 0 cả. vậy là số nguyên tố => true
  20.     return true;
  21. }
  22.  
  23. // tính tổng n số nguyên sô tố đầu tiên
  24. // value là giá trị hiện tại cần xét có phải nguyên tố không
  25. // count là số số nguyên tố đã tìm được từ 0 đến value
  26. // n là số số nguyên tố cần tính tổng
  27. int sum(int value, int count, int n)
  28. {
  29.     // nếu số số nguyên tố hiện tại đã bằng số số nguyên tố cần tìm thì trả về 0
  30.     if (count == n)
  31.         return 0;
  32.  
  33.     // kiểm tra value có phải nguyên tố không, nếu phải thì tổng với các số đã tìm được trước đó và các số tiếp theo
  34.     // đồng thời tăng count lên vì ta mới tìm đc thêm 1 số nữa
  35.     if (snt(value))
  36.     {
  37.         // in value ra để xem tìm được những số nguyên tố nào
  38.         cout << value << endl;
  39.         return value + sum(value + 1, count + 1, n);
  40.     }
  41.     else
  42.     {
  43.         return sum(value + 1, count, n);
  44.     }
  45. }
  46.  
  47.  
  48.  
  49. void main()
  50. {
  51.     // in va tinh tong 10 so nguyen to dau tien
  52.     cout << sum(0, 0, 10);
  53. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement