Advertisement
MaxObznyi

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.  
Advertisement
RAW Paste Data Copied
Advertisement