Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- const long long MAX_SIZE = 1000001;
- vector<long long >isprime(MAX_SIZE, true);
- vector<long long >prime;
- vector<long long >SPF(MAX_SIZE);
- void manipulated_seive(int N)
- {
- isprime[0] = isprime[1] = false ;
- for (long long int i=2; i<N ; i++)
- {
- if (isprime[i])
- {
- prime.push_back(i);
- SPF[i] = i;
- }
- for (long long int j=0;
- j < (int)prime.size() &&
- i*prime[j] < N && prime[j] <= SPF[i];
- j++)
- {
- isprime[i*prime[j]]=false;
- SPF[i*prime[j]] = prime[j] ;
- }
- }
- }
- int main()
- {
- int m;
- double a,b;
- while(cin>>m>>a>>b)
- {
- if(m==0&&a==0&&b==0)
- return 0;
- manipulated_seive((m+1)/2 +1);
- //cout<<prime.size()<<endl;
- double range=a/b;
- //cout<<range<<endl;
- int maxans=0;
- int p1,p2;
- for(int i=prime.size()-1; i>=0; i--)
- {
- int hi=i,lo=0;
- int x=prime[i];
- //cout<<x<<endl;
- int mid;
- double r;
- int f=0;
- while(lo<=hi){
- mid=(hi+lo)/2;
- r=prime[mid]/(double)x;
- //cout<<r<<endl;
- if(r<range){
- if(x*prime[mid]>m){
- f=1;
- break;
- }
- else{
- lo=mid+1;
- }
- }
- else{
- if(x*prime[mid]>m)
- hi=mid-1;
- else
- lo=mid+1;
- }
- }
- if(!f){
- int ans=x*prime[hi];
- double d=(double)prime[hi]/x;
- if(ans>maxans&&ans<=m&&d>=range){
- maxans=ans;
- p1=x;
- p2=prime[hi];
- }
- }
- //cout<<endl;
- }
- cout<<p2<< ' '<<p1<<endl;
- prime.clear();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment