Prime factorization problem optimized approach

#1

how the code in this problem is skipping non prime numbers although we are iterating over all the numbers

#2

hi @mohitshendre2609
this is Optimized_Approach

void Optimized_Approach(int N) {

	vector<pair<int , int>> factors;
	int i;
	for (i = 2; i * i <= N; i++) {
		if (N % i == 0) {
			int cnt = 0;
			while (N % i == 0) {
				cnt++;
				N = N / i;
			}
			factors.push_back({i, cnt});
		}
	}
	if (N != 1)factors.push_back({N, 1});

	for (auto p : factors) {
		cout << p.first << "^" << p.second << " X ";
	}

}

in this Approach we are not skipping non-prime nos
we are optimising our Naive_Approach by iterating till sqrt(n)

at end if no is not 1 and not divisible by any no till sqrt(n) means it is prime so we also add it to factors

i hope this help
if you have more doubts regarding this feel free to ask
if your doubt is resolved mark it as resolved from your doubt section inside your course