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]++;
}
}
}
Sieve of Eratosthenes
The prime factorization part is also called Sieve of Erathosthenes?
I think there is no name for this method. This problem can be solved by using only the above approach.
try to solve this.
This problem
It's called Prime Power Factorization(PPF).