Guest User

Untitled

a guest
Jul 20th, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.91 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include<vector>
  4. #include<algorithm>
  5. #include<math.h>
  6. #include<cstring>
  7. #include<map>
  8. #include<set>
  9. #include <cctype>
  10. #include <cmath>
  11. #include <cstdio>
  12. #include<string>
  13. using namespace std;
  14. int comp[10000001];
  15. void sieve() {
  16. comp[0] = comp[1] = 0;
  17. for (int i = 2; i <= 5e6; ++i) {
  18. if (!comp[i]) {
  19. //primes.push_back(i);
  20. for (int j = i + i; j <= 5e6; j += i) {
  21. int n = j;
  22. while (n%i == 0) {
  23. comp[j]++;
  24. n /= i;
  25. }
  26. }
  27. comp[i] = 1;
  28. }
  29. }
  30. for (int i = 3; i <= 5e6; ++i)
  31. comp[i] += comp[i - 1];
  32. //cout << comp[5000000] << endl;
  33. }
  34.  
  35. int main() {
  36. int a, b;
  37. sieve();
  38. int css = 1;
  39. scanf("%d", &a);
  40. while (a>=0) {
  41. int ans = lower_bound(comp, comp + 5000001, a) - comp;
  42. if (ans == 5000001||comp[ans] != a)
  43. printf("Case %d: Not possible.\n",css);
  44. else
  45. printf("Case %d: %d!\n",css, ans);
  46. scanf("%d", &a);
  47. css++;
  48. }
  49.  
  50. system("pause");
  51. }
Add Comment
Please, Sign In to add comment