There should be a better approach to improve the time complexity.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <cmath> #define ull unsigned long long #define ll long long using namespace std; bool prime[35000000]; vector<int> prm; int main() { double n; int mxprime,cnt; ull num; for(int i=2;i<35000000;i++) { if(prime[i]==0) { prm.push_back(i); for(int j=i+i;j<35000000;j+=i) { prime[j]=1; } } } while(scanf("%lf",&n),n!=0) { mxprime=-1; if(n<0) num=n*(-1); else num=n; if(n==1 || n==2 || n==3) { printf("-1\n"); } else { int idx=prm.size(); cnt=0; for(int i=0;i<idx;i++) { if(num<prm[i]) break; if(num%prm[i]==0) { mxprime= (mxprime>prm[i]?mxprime:prm[i]); cnt+=1; } while(num%prm[i]==0) { num/=prm[i]; } } if(num==1) { if(n!=mxprime) { if(cnt>1) printf("%d\n",mxprime); else printf("-1\n"); } else printf("-1\n"); } else { if(mxprime<num) printf("%llu\n",num); else { if(cnt>1) printf("%d\n",mxprime); else printf("-1\n"); } } } } return 0; } |