583 - Prime Factors

Apr 13th, 2021
714
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define Niloy
3. #define int int64_t
4. #define MAX (int) 1e7 + 123
5. #define MOD 1e9
6. #define pb push_back
7. #define pairs pair<int, int>
8. #define vi vector<int>
9. #define vb vector<bool>
10. #define vii vector<pairs>
11. #define lb lower_bound
12. #define ub upper_bound
13. #define endl '\n'
14. #define llu unsigned long long
15. using namespace std;
16. /* ----------------------------------------------------------------------------------- */
17.
18. // Input/Output
19. #define fastInput ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
20. #define all(x) x.begin(), x.end()
21. #define square(a) (a * a)
22. #define mem(a, b) memset(a, b, sizeof(a))
23.
24. // Fractional Number
25. #define fraction()        cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield);
26.
27. #define scan(a)           scanf("%lld", &a);
28. #define scan2(a, b)       scanf("%lld %lld", &a, &b);
29. #define scan3(a, b, c)    scanf("%lld %lld %lld", &a, &b, &c);
30. #define scan4(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
31.
32. #define scanD(a)          scanf("%lf", &a);
33. #define scanD2(a, b)      scanf("%lf %lf", &a, &b);
34. #define scanD3(a, b, c)   scanf("%lf %lf %lf", &a, &b, &c);
35. #define scanD4(a, b, c, d)scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
36.
37.
38. #define print(a)           printf("%lld\n", a);
39. #define print2(a, b)       printf("%lld %lld\n", a, b);
40. #define print3(a, b, c)    printf("%lld %lld %lld\n", a, b, c);
41. #define print4(a, b, c, d) printf("%lld %lld %lld %lld\n", a, b, c, d);
42.
43. #define printD(a)          printf("%lf\n", a);
44. #define printD2(a, b)      printf("%lf %lf\n", a, b);
45. #define printD3(a, b, c)   printf("%lf %lf %lf\n", a, b, c);
46. #define printD4(a, b, c, d)printf("%lf %lf %lf %lf\n", a, b, c, d);
47. #define printTwoD(a)       printf("%.2lf\n", a);
48.
49. // File I/O
50. #define read(x)  freopen(x, "r", stdin);
51. #define write(x) freopen(x, "w", stdout);
52.
53. // Loops
54. #define rep(i, a, n) for (int i = a; i < n; i++)
55. #define REP(i, a, n) for (int i = a; i <= n; i++)
56. #define rev(i, n, a) for (int i = n - 1; i >= a; i--)
57. #define REV(i, n, a) for (int i = n; i >= a; i--)
58. #define inputArray(a,n) rep(i, 0, n) cin >> a[i];
59. #define copyArray(a,temp,n) rep(i, 0, n) temp[i]=a[i];
60. #define printArray(a,n) rep(i, 0, n) cout << a[i] << " "; cout << endl;
61.
62. /* ----------------------------------------------------------------------------------- */
63.
64. #define Cases  cout << "Case " << ++Case << ": ";
65. #define __test int tt; int Case=0; cin >> tt; while(tt--)
66. #define showTime cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
67.
68. #define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, m){cout<<A[i][j]<<"";}cout<<"\n";}cout<<"\n";}
69. #define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
70. #define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}
71.
72. /* ----------------------------------------------------------------------------------- */
73.
74. int gcd(int n, int m) { return m ? gcd(m, n % m) : n; }
75. int lcm(int n, int m) { return n / gcd(n, m) * m; }
76.
77. struct debugger {
78.     typedef string::iterator si;
79.     static void call(si it, si ed) {}
80.     template<typename T, typename ... aT>
81.     static void call(si it, si ed, T a, aT... rest) {
82.         string b;
83.         for(; *it!=','; ++it)
84.             if(*it!=' ')
85.                 b+=*it;
86.         cout << b << "=" << a << " ";
87.         call(++it, ed, rest...);
88.     }
89. };
90.
91. /* ----------------------------------------------------------------------------------- */
92. void input() {
93. #ifdef Niloy
95.     write("output.txt");
96. #endif
97. }
98.
99. /* ----------------------------------------------------------------------------------- */
100.
101.
102. bitset<MAX> isPrime;
103. vi Prime;
104.
105. void primeGen(int n) {      // O(N)
106.     for (int i = 3; i <= n; i += 2) {
107.         isPrime[i] = 1;
108.     }
109.     isPrime[2] = 1;
110.     int sq = sqrt(n);
111.
112.     for (int i = 3; i <= sq; i += 2) {
113.         if (isPrime[i]) {
114.             for (int j = i * i; j <= n; j += (i * 2)) {
115.                 isPrime[j] = 0;
116.             }
117.         }
118.     }
119.
120.     Prime.pb(2);
121.     for (int i = 3; i <= n; i += 2) {
122.         if (isPrime[i]) {
123.             Prime.pb(i);
124.         }
125.     }
126. }
127.
128. vi factorization(int n) {
129.     vi ans;
130.
131.     for (auto p : Prime) {
132.         if (p * p > n) {
133.             break;
134.         }
135.         if (n % p == 0) {
136.             while (n % p == 0) {
137.                 ans.pb(p);
138.                 n /= p;
139.             }
140.         }
141.     }
142.     if (n > 1) {
143.         ans.pb(n);
144.     }
145.     return ans;
146. }
147.
148. void solve() {
149.     int lim = 1e7;
150.     primeGen(lim);
151.
152.     int n;
153.     while (cin >> n && n) {
154.         vi ans;
155.         if (n < 0) {
156.             int a = -1 * n;
157.             ans = factorization(a);
158.         } else {
159.             ans = factorization(n);
160.         }
161.
162.         cout << n << " = ";
163.         if (n < 0) {
164.             cout << "-1 x ";
165.         }
166.         rep(i, 0, ans.size()) {
167.             if (i == (ans.size() - 1)) {
168.                 cout << ans[i] << endl;
169.             } else {
170.                 cout << ans[i] << " x ";
171.             }
172.         }
173.     }
174. }
175.
176. int32_t main() {
177.     // input();
178.     // fastInput;
179.     solve();
180.
181.     // __test {
182.     //  solve();
183.     // }
184.
185.     // showTime;
186.     return 0;
187. }
188.
RAW Paste Data