Atcoder Beginner Contest 284 D - Happy New Year 2023 Solution

  Problem Link:  https://atcoder.jp/contests/abc284/tasks/abc284_d

Solution in C++:

1. /// La ilaha illellahu muhammadur rasulullah
2. ///******Bismillahir-Rahmanir-Rahim******///
3. /// Abul Hasnat Tonmoy
4. /// Department of CSE,23rd batch
5. /// Islamic University,Bangladesh
6. ///**********ALLAH IS ALMIGHTY************///
7. #include <bits/stdc++.h>
8. using namespace std;
9. #define ll long long int
10. #define N 9000009
11. vector<ll> prime;
12. ll i, j;
13. bool vis[N];
14. void sieve() {
15. for (i = 3; i * i <= N; i += 2) {
16. if (vis[i] == 0) {
17. for (j = i * i; j <= N; j += 2 * i) {
18. vis[j] = 1;
19. }
20. }
21. }
22. prime.push_back(2);
23. for (i = 3; i <= N; i += 2) {
24. if (vis[i] == 0) {
25. prime.push_back(i);
26. }
27. }
28. }
29. int main() {
30. ll t, n, i, mx, cnt, cn, cp;
31. sieve();
32. int sz = prime.size();
33. cin >> t;
34. while (t--) {
35. cin >> n;
36. ll a, b, p, q;
37. for (i = 0; i <= sz; i++) {
38. if (n % prime[i] == 0) {
39. if (n % (prime[i] * prime[i]) == 0) {
40. q = n / (prime[i] * prime[i]);
41. p = prime[i];
42. } else {
43. q = prime[i];
44. p = sqrt(n / q);
45. }
46. break;
47. }
48. }
49. cout << p << " " << q << endl;
50. }
51. }