primeFactors

{
	"": {
		"prefix": "cd_primeFactor",
		"body": [
			"const int N = 2e5 + 10;",
			"vector<bool> isPrime(N, 1);",
			"vector<int> hp(N, 0);",
			"",
			"// call sieve() in main",
			"void sieve(){",
			"    isPrime[0] = isPrime[1] = 0;",
			"",
			"    for(int i = 2; i < N; i++){",
			"        if(isPrime[i]){",
			"            hp[i] = i;",
			"",
			"            for(int j = 2 * i; j < N; j += i) {",
			"                isPrime[j] = 0;",
			"                hp[j] = i;",
			"            }",
			"        }",
			"    }",
			"}",
			"",
			"vector<pair<int, int>> primeFactors(int n){",
			"    vector<pair<int,int>> prime_factors;",
			"",
			"    while(n > 1){",
			"        int prime_factor = hp[n];",
			"        int ct= 0;",
			"",
			"        while(n % prime_factor == 0) {",
			"            n /= prime_factor;",
			"            ct++;",
			"        }",
			"",
			"        // ct -> number of prime_factor in 'n'",
			"        prime_factors.push_back({prime_factor, ct});",
			"    }",
			"",
			"    reverse(prime_factors.begin(), prime_factors.end());",
			"",
			"    return prime_factors;",
			"}"
		],
		"description": ""
	}
}