UVa 10139 - Factovisors Solution

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
using namespace std;
bitset<46341> p;
vector<int> prime;
void calc(){
    for(int i=2;i<46341;i++){
        if(!p[i]){
            prime.push_back(i);
            if(i<=216)
                for(int j=i*i;j<46341;j+=i)
                    p[j]=1;
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0);
        calc();
        int m,n;
        while(cin>>n>>m){
            int M=m;
            int flag=0;
            if(n>=m){
                cout<<m<<" divides "<<n<<'!'<<endl;
                continue;
            }
            vector<vector<int> > p1;
            int sqr=sqrt(m);
            for(int i=0;i<prime.size()&&prime[i]<=m&&m>1;i++)
                if(m%prime[i]==0){
                    int num=0;
                    while(m%prime[i]==0){
                        num++;
                        m/=prime[i];
                    }
                    p1.push_back({prime[i],num});
                }
            if(m>1){
                if(m>n){
                    cout<<M<<" does not divide "<<n<<'!'<<endl;
                    continue;
                }
                else
                    p1.push_back({m,1});
            }
            for(int i=0;i<p1.size()&&flag==0;i++){
                int ans=0;
                long long b=p1[i][0],e=p1[i][0];
                while(b<=n){
                    ans+=n/b;
                    b*=e;
                }
                if(ans<p1[i][1])
                    flag=1;
            }
            if(flag)
                cout<<M<<" does not divide "<<n<<'!'<<endl;
            else
                cout<<M<<" divides "<<n<<'!'<<endl;
            }
        }