fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 100000
  4. bool status[N+1];
  5. vector<int>primes;
  6. //can store upto 664578 primes
  7. void seive(){
  8.     int i,j,total=1,len;
  9.     primes.push_back(2);
  10.     len=sqrt(N);
  11.     for(i=3;i<=len;i+=2){
  12.         if(!status[i]){
  13.             for(j=i*i;j<=N;j+=i)status[j]=true;
  14.         }
  15.     }
  16.     for(i=3;i<=N;i+=2){
  17.         if(!status[i]){
  18.             primes.push_back(i);
  19.             total++;
  20.         }
  21.     }
  22.     //return total;
  23. }
  24. vector<int>numPF(int n){
  25.     vector<int>facts;
  26.     int pf_idx=0,pf=primes[pf_idx],ans=0;
  27.     while(pf*pf<=n){
  28.         if(n%pf==0){
  29.             facts.push_back(pf);
  30.             while(n%pf==0)n/=pf;
  31.         }
  32.         pf=primes[++pf_idx];
  33.     }
  34.     if(n!=1)facts.push_back(n);
  35.     return facts;
  36. }
  37. pair<int,int>sqrechk(int x){
  38.     int a,b;
  39.     a=0,b=x;
  40.     while(a<=b){
  41.         if(a*a+b*b==x)return make_pair(a,b);
  42.         else if(a*a+b*b>x)b--;
  43.         else a++;
  44.     }
  45.     return make_pair(-1,-1);
  46. }
  47. typedef pair<int,int> ii;
  48. int main(){
  49.     seive();
  50.     int n,i,sz,cases=0;
  51.     while(scanf("%d",&n)!=EOF){
  52.         vector<int>facts;
  53.         facts=numPF(n);
  54.         sz=facts.size();
  55.         vector<ii>ans;
  56.         printf("Case #%d: ",++cases);
  57.         //for(i=0;i<facts.size();i++)cout<<facts[i]<<" ";
  58.         if(sz==0)printf("\n");
  59.         else{
  60.             for(i=0;i<sz;i++){
  61.                 if(facts[i]%4==3)ans.push_back(ii(facts[i],0));
  62.                 else ans.push_back(sqrechk(facts[i]));
  63.             }
  64.             sz=ans.size();
  65.             for(i=0;i<sz-1;i++){
  66.                 if(ans[i].second==0)printf("%d, ",ans[i].first);
  67.                 else if(ans[i].second==1)printf("%d+j, %d-j, ",ans[i].first,ans[i].first);
  68.                 else printf("%d+%dj, %d-%dj, ",ans[i].first,ans[i].second,ans[i].first,ans[i].second);
  69.             }
  70.             if(ans[sz-1].second==0)printf("%d\n",ans[sz-1].first);
  71.             else if(ans[sz-1].second==1)printf("%d+j, %d-j\n",ans[sz-1].first,ans[sz-1].first);
  72.             else printf("%d+%dj, %d-%dj\n",ans[sz-1].first,ans[sz-1].second,ans[sz-1].first,ans[sz-1].second);
  73.         }
  74.     }
  75.     return 0;
  76. }
  77.  
  78.  
Success #stdin #stdout 0s 15336KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/HkPWSw
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!