fork(1) download
  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  4.  
  5.  
  6. int main()
  7. {
  8. int n, m;
  9. const int MAXN = 10000001;
  10. bool simple[MAXN];
  11. for(int i = 2; i <= MAXN; i++){
  12. simple[i] = true;
  13. }
  14. for(int i = 2; i <= sqrt(MAXN); i++){
  15. if(simple[i]){
  16. for(int j = i * i; j <= MAXN; j += i){
  17. simple[j] = false;
  18. }
  19. }
  20. }
  21.  
  22. int count[MAXN];
  23. int lastSum = 0;
  24. for(int i = 1; i < MAXN; i++){
  25. count[i] = lastSum + simple[i];
  26. lastSum = count[i];
  27. }
  28. while(cin >> m >> n){
  29. int answer = count[n] - count[m] + simple[m];
  30. cout << answer << endl << endl;
  31. }
  32. }
Success #stdin #stdout 0.09s 51928KB
stdin
77 777

55 555

33 333
stdout
116

85

56