PrimeFactorization.cpp

//Code Courtesy: Sakib vai.. :D
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int SIZE = 1e6 + 10;
bool status[SIZE];
vector<int>prime;
vector<int>divi;
int factor[SIZE], power[SIZE];
int mobius[SIZE];

void sieve() {
	memset(status, 1, sizeof(status));
	for (int i = 2; i < SIZE; i++) {
		if (status[i] == 1) {
			for (int j = 2 * i; j < SIZE; j += i) {
				status[j] = 0;
			}
		}
	}
	for (int i = 2; i <= SIZE; i++) {
		if (status[i] == 1) {
			prime.push_back(i);
		}
	}
}
int psz; int divsz;
void mob(int N) {
	/*
			1 if n is a square-free positive integer with an even number of prime factors.
			-1 if n is a square-free positive integer with an odd number of prime factors.
			0 if n has a squared prime factor.
	*/
	memset(mobius, -1, sizeof(mobius));
	memset(status, 0, sizeof(status));
	int sq = sqrt(N);
	for (int i = 1; i <= sq; i++) {
		mobius[i*i] = 0;
	}
	for (int i = 2; i <= N; i++) {
		if (status[i] == 0) {
			for (int j = 2 * i; j <= N; j += i) {
				if (mobius[j] == 0)
					continue;
				mobius[j] = -1 * mobius[j / i];
				status[j] = 1;
			}
		}
	}
}

void primefactor(long long N) {
	int sq = sqrt(N);
	psz = 0;
	for (int i = 0; i<prime.size() && prime[i] <= sq; i++) {
		//cout<< "i: "<<i<<endl;
		//cout<<N<<endl;
		int cnt = 0;
		while (N%prime[i] == 0) {
			N /= prime[i];
			cnt++;
		}
		factor[psz] = prime[i];
		power[psz] = cnt;
		psz++;
		sq = sqrt(N);
	}
	if (N>1) {
		factor[psz] = N;
		power[psz] = 1;
		psz++;

	}

	for (int i = 0; i<psz; i++) {
		if (power[i]>0)
			cout << factor[i] << " " << power[i] << endl;
	}

	divi.push_back(1);
	divsz = 1;
	long long tempsz;
	for (int i = 0; i<psz; i++) {
		long long x = 1;
		int tempsz = divsz;
		for (int j = 1; j <= power[i]; j++) {

			x = x*factor[i];
			///cout<<x<<endl;
			for (int k = 0; k<tempsz; k++) {
				divi.push_back(divi[k] * x);
				//cout<<"Div Size: "<<divi.size()<<endl;
				divsz = divi.size();
			}
		}
	}
	sort(divi.begin(), divi.end());
	for (int i = 0; i<divi.size(); i++) {
		cout << divi[i] << " ";
	}
	cout << endl;
}

int main() {
	sieve();
	/*
	for(int i=0;i<10;i++)
	cout<<prime[i]<<endl;*/
	long long n;
	while (cin >> n) {
		primefactor(n);
		mob(n);
		int cnt = 0;
		for (int i = 0; i<n; i++) {
			if (mobius[i] == 0) {
				cnt++;
				cout << i << endl;
			}
		}
		cout << cnt << endl;
	}
}