# divisors+prime+factorization

May 21st, 2022
748
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #define int long long
3. using namespace std;
4.
5. void print_div(int n) {
6.     for (int a = 1; a * a <= n; a++)
7.         if (n % a == 0) {
8.             cout << a << ' ' << n / a << ' ';
9.         }
10. }
11. ///primality test
12. bool is_prime(int n) {
13.     if (n == 1)
14.         return 0;
15.     for (int a = 2; a * a <= n; a++)
16.         if (n % a == 0) {
17.             return 0;
18.         }
19.     return 1;
20. }
21.
22. void factorization(int n) {
23.     int initialN = n;
24.     for (int p = 2; p * p <= initialN; p++)
25.         if (n % p == 0) {
26.             ///try to use it
27.             int cnt = 0;
28.             while (n % p == 0) {
29.                 n = n / p;
30.                 cnt++;
31.             }
32.             cout << "Number " << p << " appears " << cnt << " times.\n";
33.         }
34.     ///n from which we removed all primes <= sqrt(initial n)
35.     ///n = 1 -- no prime numbers left
36.     ///n > 1 ---> n = p[i] which is large, > sqrt(initial n)
37.     if (n > 1)
38.         cout << "Number " << n << " appears " << 1 << " times.\n";
39. }
40.
41. signed main()
42. {
43.     int n;
44.     cin >> n;
45.     factorization(n);
46.     //cout << is_prime(n);
47.     //print_div(n);
48.     return 0;
49. }
50.