Prime Factorization

#include<bits/stdc++.h>
using namespace std;

const int maxN = 10000;
int64_t isVisited[maxN / 64 + 200];
vector<int> primes;
void Sieve_of_Eratosthenes(int limit) {
	limit += 100;
	for (int64_t i = 3; i <= sqrt(limit) ; i += 2) {
		if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
			for (int64_t j = i * i; j <= limit; j += 2 * i) {
				isVisited[j / 64] |= (1LL << (j % 64));
			}
		}
	}
	primes.push_back(2);
	for (int64_t i = 3; i <= limit; i += 2) {
		if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
			primes.push_back(i);
		}
	}
}

bool is_prime(int n) {
	if (n < 2) return false;
	if (n == 2) return true;
	if (n % 2 == 0) return false;
	if (!(isVisited[n / 64] & (1LL << (n % 64)))) return true;
	return false;
}

int number_of_PF (int n) {
	int count = 0;
	for (int p : primes) {
		if (p * p  > n) break;
		if (n % p == 0) {
			++count;
			while (n % p == 0) n /= p;
		}
	}
	if (n > 1) ++count;
	return count;
}

vector<int> Extract_PF (int n) {
	vector<int> pf;
	for (int p : primes) {
		if (p * p  > n) break;
		if (n % p == 0) {
			pf.push_back(p);
			while (n % p == 0) n /= p;
		}
	}
	if (n > 1) pf.push_back(n);
	return pf;
}

vector<pair<int,int>> Extract_PF_with_count (int n) {
	vector<pair<int,int>> pf;
	for (int p : primes) {
		if (p * p > n) break;
		if (n % p == 0) {
			int count = 0;
			while (n % p == 0) {
				++count,n /= p;
			}
			pf.push_back(make_pair(p,count));
		}
	}
	if (n > 1) pf.push_back(make_pair(n,1));
	return pf;
}

int main () {
	 ios::sync_with_stdio(false);
	 cin.tie(nullptr);
	 cout.tie(nullptr);
	 Sieve_of_Eratosthenes(maxN);
	 int count = number_of_PF(120);
	 vector<int> pf = Extract_PF(120);
	 vector<pair<int,int>> pf_with_count = Extract_PF_with_count(120);
	 cout << "Number of Primes in PF of 120 : " << count << '\n';
	 cout << "List : \n";
	 for (int p : pf) {
		 cout << p << ' ';
	 }
	 cout << "\nList with Count\n";
	 for (pair<int,int> p : pf_with_count) {
		 cout << p.first << ' ' << p.second << '\n';
	 }
}