#include #include using namespace std; typedef unsigned int uint; const int MAX_PRIME=65536; //Sqrt(MAXINT) is the max prime we'll ever need for this problem const int SQRT_MAX_PRIME=256; //Sqrt(MAX_PRIME) - for Eratosthenes Prime Sieve const int TOTAL_PRIMES=6542; //The actual number of primes under MAX_PRIME (see comment below on how we get this number) bool isprime[MAX_PRIME+1]; //data structure to answer question of "is this a prime?" int primes[TOTAL_PRIMES+1]; //data structure to store primes under MAX_PRIME //Eratosthenes Prime Sieve void primeSieve(bool isprime[],int max_prime) { for (int i=0;i<=max_prime;i++) isprime[i]=true; //assume all isprime isprime[0]=false; isprime[1]=false; //Eratothenes Prime Sieve for (int prime=2;prime<=SQRT_MAX_PRIME;prime++) if (isprime[prime]) for (int comp=prime*prime;comp sqrt(n), then q < sqrt(n) and we've already checked for primes < sqrt(n) for (int i=0;primes[i]<=(int)sqrt((double)n);i++) if (n%primes[i]==0) return primes[i]; return 1;//cannot factor } int main() { //prepare our Prime Machine! primeSieve(isprime,MAX_PRIME); extractPrimes(isprime,primes,MAX_PRIME); uint n; while (cin>>n && n!=0) { int p=getFirstPrime(n); int q=n/p; cout<