Блог пользователя ruhan.habib39

Автор ruhan.habib39, история, 9 лет назад, По-английски

What's the name of the following algorithm:

const int MAXN = 100*1000;
unordered_map<int,int> factors[MAXN+10];
vector<bool> isprime(MAXN+10, true);
int primeFactor[MAXN+10];

void init() {
   isprime[0] = isprime[1] = false;
   for(int i = 2; i*i <= MAXN; i++) {
     if(isprime[i]) {
       for(int j = i*i; j <= MAXM; j += i) {
          isprime[j] = false;
          primeFactor[j] = i;
       }
     }
   }
   for(int i = 2; i <= MAXM; i++) {
     if(isprime[i]) factors[i][i] = 1;
     else {
       int dv = primeFactor[i];
       factors[i] = factors[i/dv];
       factors[i][dv]++;
     }
   }
}
  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

try to solve this.

This problem

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's called Prime Power Factorization(PPF).