fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  3. using namespace std;
  4.  
  5. bool is_prime(int n, int divisor = 2) {
  6.     if (n <= 2) return (n == 2);
  7.     if (n % divisor == 0) return false;
  8.     if (divisor * divisor > n) return true;
  9.     return is_prime(n, divisor + 1);
  10. }
  11.  
  12. int count_primes(int start, int end) {
  13.     if (start > end) return 0;
  14.     return is_prime(start) + count_primes(start + 1, end);
  15. }
  16.  
  17. // For large ranges (like [10, 5000000]), this recursive approach will stack overflow
  18. // Use Sieve of Eratosthenes with optimizations for large ranges
  19.  
  20. // int count_primes(int start, int end) {
  21. //     if (start > end) return 0;
  22. //     if (end < 2) return 0;
  23. //
  24. //     // Adjust start to at least 2
  25. //     start = max(2, start);
  26. //
  27. //     // Sieve of Eratosthenes
  28. //     vector<bool> is_prime(end + 1, true);
  29. //     is_prime[0] = is_prime[1] = false;
  30. //
  31. //     for (int p = 2; p * p <= end; ++p) {
  32. //         if (is_prime[p]) {
  33. //             for (int multiple = p * p; multiple <= end; multiple += p) {
  34. //                 is_prime[multiple] = false;
  35. //             }
  36. //         }
  37. //     }
  38. //
  39. //     // Count primes in [start, end]
  40. //     int count = 0;
  41. //     for (int i = start; i <= end; ++i) {
  42. //         if (is_prime[i]) ++count;
  43. //     }
  44. //
  45. //     return count;
  46. // }
  47. void solve() {
  48.    cout << count_primes(10, 20) << endl;
  49.     cout << count_primes(10, 200) << endl;
  50. }
  51.  
  52. int main() {
  53.     IOS;
  54.     solve();
  55.     return 0;
  56. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4
42
https://ideone.com/yRhBUn
language:
C++14 (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!