fork download
copy 
  1. #include <cstdio>
  2. #include <bitset> // compact STL for Sieve, more efficient than vector<bool>!
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8. typedef vector<int> vi;
  9.  
  10.  
  11. ll _sieve_size; // ll is defined as: typedef long long ll;
  12. bitset<10000010> bs; // 10^7 should be enough for most cases
  13. vi primes; // compact list of primes in form of vector<int>
  14.  
  15. void sieve(ll upperbound) { // create list of primes in [0..upperbound]
  16.     _sieve_size = upperbound + 1; // add 1 to include upperbound
  17.     bs.set(); // set all bits to 1
  18.     bs[0] = bs[1] = 0; // except index 0 and 1
  19.     for (ll i = 2; i <= _sieve_size; i++) if (bs[i]) {
  20.         // cross out multiples of i starting from i * i!
  21.         for (ll j = i * i; j <= _sieve_size; j += i) bs[j] = 0;
  22.              primes.push_back((int)i); // also add this vector containing list of primes
  23.     } } // call this method in main method
  24.  
  25. bool isPrime(ll N) { // a good enough deterministic prime tester
  26.     if (N <= _sieve_size) return bs[N]; // O(1) for small primes
  27.     for (int i = 0; i < (int)primes.size(); i++)
  28.         if (N % primes[i] == 0) return false;
  29.      return true; // it takes longer time if N is a large prime!
  30. }
  31.  
  32. vi primeFactors(ll N) { // remember: vi is vector<int>, ll is long long
  33.    vi factors;
  34.    ll PF_idx = 0, PF = primes[PF_idx]; // using PF = 2, then 3,5,7,... is also ok
  35.    while (N != 1 && (PF * PF <= N)) { // stop at sqrt(N), but N can get smaller
  36.        while (N % PF == 0) { N /= PF; factors.push_back(PF); } // remove this PF
  37.        PF = primes[++PF_idx]; // only consider primes!
  38.    }
  39.  
  40.    if (N != 1) factors.push_back(N); // special case if N is actually a prime
  41.    return factors; // if N does not fit in 32-bit integer and is a prime number
  42. }
  43.  
  44. ll abss(ll a){
  45.     if(a < 0){
  46.          a = 0 - a;
  47.     }
  48.     return a;
  49. }
  50.  
  51. int main(){
  52.     sieve(10000000);
  53.     ll t;
  54.     while(true){
  55.         scanf("%lld", &t);
  56.  
  57.         if(!t) break;
  58.  
  59.         ll N = abss(t);
  60.         vi fac = primeFactors(N);
  61.         printf("%lld = ", t);
  62.         if(t < 0){
  63.              printf("%d x %d", -1, fac[0]);
  64.         }else{
  65.             printf("%d", fac[0]);
  66.         }
  67.  
  68.         for(int i = 1; i < fac.size(); i++){
  69.             printf(" x %d", fac[i]);
  70.         }
  71.         printf("\n");
  72.     }
  73. }
  74.  
Success #stdin #stdout 0.17s 4456KB
comments (?)
stdin
copy 
2147483647
2147483648
2147483649
-190
-191
-192
-193
-194
195
196
197
198
199
200
0
stdout
copy 
2147483647 = 2147483647
2147483648 = 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2 x 2
2147483649 = 3 x 715827883
-190 = -1 x 2 x 5 x 19
-191 = -1 x 191
-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
-193 = -1 x 193
-194 = -1 x 2 x 97
195 = 3 x 5 x 13
196 = 2 x 2 x 7 x 7
197 = 197
198 = 2 x 3 x 3 x 11
199 = 199
200 = 2 x 2 x 2 x 5 x 5
https://ideone.com/IQy6Lr
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!