fork download
copy 
  1. /*
  2. 1<=A<=B<=100000000000000
  3. 소수의 N제곱꼴이면 거의 소수
  4. 최대 10^14이므로...
  5. 1 1000
  6. 2 4 8 16 32 64 128 256 512
  7. 3 9 27 81 243 729
  8. 5 25 125 625
  9. 7 49 343
  10. 11 121
  11. 13 169
  12. 17 ..
  13. 19 ..
  14. 23 ..
  15. 29 ..
  16. 31 ..
  17. == 25
  18. ...
  19. k번 제곱했을 때 범위를 벗어날때까지 반복?
  20.  */
  21. #include <iostream>
  22. #include <set>
  23. using namespace std;
  24. typedef unsigned long long int ULL;
  25.  
  26. int main() {
  27.     bool not_prime[10000001];
  28.     for (int i = 2; i < 10000000; i++) {
  29.         for (int j = 2 * i; j <= 10000000; j += i) {
  30.             not_prime[j] = true;
  31.         }
  32.     }
  33.     long long A, B, i = 2;
  34.     cin >> A >> B;
  35.     int cnt = 0;
  36.     set<ULL> s;
  37.     while (1) {
  38.         if (i * i > B) {
  39.             break;
  40.         }
  41.         if (!not_prime[i]) {
  42.             ULL T = i * i;
  43.             // long long 보다 커지게 되는 경우를 방지해야함
  44.             while (T <= B && B > 18446744073709551615UL / T) {
  45.                 if (A <= T && T <= B && s.find(T) == s.end()) {
  46.                     s.emplace(T);
  47.                     cnt++;
  48.                 }
  49.                 T *= i;
  50.             }
  51.         }
  52.         i++;
  53.     }
  54.     cout << cnt;
  55.     return 0;
  56. }
  57.  
Success #stdin #stdout 0.52s 13256KB
comments (?)
stdin
copy 
1 1000
stdout
copy 
Standard output is empty
https://ideone.com/DLKWxc
language:
C++ (gcc 8.3)
created:
5 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!