fork download
copy 
  1. /*Cho số tự nhiên N. Nhiệm vụ của bạn là hãy đếm tất cả các số từ 1 tới N mà có đúng ba ước số. Ví dụ N=100, ta có các số 4, 9, 25, 49.
  2.  
  3. Input:
  4.  
  5. Dòng đầu tiên đưa vào số lượng test T.
  6. Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là một số N.
  7. T, N thỏa mãn rang buộc 1≤T≤100; 1≤N ≤1012.
  8. Output:
  9.  
  10. Đưa ra kết quả mỗi test theo từng dòng.*/
  11.  
  12. #include <bits/stdc++.h>
  13. using namespace std;
  14.  
  15. #define ll long long
  16. #define ull unsigned long long
  17. #define fi first
  18. #define se second
  19. const int mod = 1000000007;
  20.  
  21. int prime[10000001];
  22. int p = 10000000;
  23.  
  24. void sang(){
  25. 	for(int i = 0; i <= p; i++){
  26. 		prime[i] = 1;
  27. 	}
  28. 	prime[0] = prime[1] = 0;
  29. 	for(int i = 2; i <= sqrt(p); i++){
  30. 		if(prime[i] == 1){
  31. 			for(int j = i * i; j <= p; j += i){
  32. 				prime[j] = 0;
  33. 			}
  34. 		}
  35. 	}
  36. }
  37.  
  38. int main(){
  39. 	ios::sync_with_stdio(false);
  40. 	cin.tie(nullptr);
  41.  
  42. 	sang();
  43. 	int t; cin >> t;
  44. 	while(t--){
  45. 		ll n; cin >> n;
  46. 		int dem = 0;
  47. 		for(int i = 2; i <= sqrt(n); i++){
  48. 			if(prime[i] == 1){
  49. 				if(i * i <= n) ++dem;
  50. 			}
  51. 		}
  52. 		cout << dem << endl;
  53. 	}
  54. 	return 0;
  55. }
Success #stdin #stdout 0.13s 42556KB
comments (?)
stdin
copy 
2
50
200
stdout
copy 
4
6
https://ideone.com/PGbU60
Đếm số có 3 ước
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!