Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- bool mark[2000000];
- vector<ll>isprime;
- void sieve()
- {
- mark[0]=true;
- mark[1]=true;
- for(ll i=2; i*i<=1000005; i++)
- {
- if(mark[i]==false)
- {
- for(ll j=i*i; j<=1000005; j+=i)
- {
- mark[j]=true;
- }
- }
- }
- for(ll i=2;i<1000005;i++)
- {
- if(mark[i]==false)
- isprime.push_back(i);
- }
- }
- bool factor(ll n,ll m)
- {
- ll a,b,c,d,i,j,k;
- a=sqrt(m);
- vector< pair<ll,ll> >v;
- for(i=0; i<isprime.size(); i++)
- {
- if(isprime[i]>a)
- break;
- if(m%isprime[i]==0)
- {
- ll cnt=0;
- while(m%isprime[i]==0)
- {
- m/=isprime[i];
- cnt++;
- }
- v.push_back(make_pair(isprime[i],cnt));
- }
- }
- if(m>1)
- v.push_back(make_pair(m,1));
- for(auto t: v)
- {
- c=n;
- ll cnt=0;
- while(c)
- {
- c/=t.first;
- cnt+=c;
- }
- if(cnt<t.second)
- return false;
- }
- return true;
- }
- int main()
- {
- sieve();
- ll n,m,i,j,k;
- while(cin>>n>>m)
- {
- if(factor(n,m)==true)
- cout<<m<<" divides "<<n<<"!"<<endl;
- else
- cout<<m<<" does not divide "<<n<<"!"<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement