Algorithm to find GCD using Stein’s algorithm gcd(a,b) If both and b are 0, gcd is zero gcd(0, 0) = 0. gcd(a, 0) = a and gcd(0, b) = b because everything divides 0. If a and b are both even, gcd(a, b) = 2*gcd(a/2, b/2) because 2 is a common divisor. Multiplication with 2
Category: Number Theory
Almost Prime number
Problem:A no is said to be k-Almost Prime Number if it has exactly k prime factors (not necessary distinct). Your task is to complete the functionprintKAlmostPrimes which takes two argument k and N and prints the first N numbers that are k prime. Problem Link
|
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 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
/*You are required to complete this function*/ bool isPrime(int n) { bool arr[20]; int i; arr[2]=1;arr[3]=1;arr[5]=1;arr[7]=1; arr[11]=1;arr[13]=1;arr[17]=1;arr[19]=1; if(n<20) { if(arr[n]==1) return 1; else if(arr[n]==0) return 0; } if(n%2==0) return 0; for(i=3;i<=sqrt(n);i+=2) { if(n%i==0) return 0; } return 1; } int CountOfPrime(int n) { int cnt=0,i; while(n%2==0) { cnt+=1; n/=2; } for(i=3;i<=sqrt(n);i+=2) { if(isPrime(i)==0) continue; while(n%i==0) { cnt+=1; n/=i; } } if(n>2) cnt+=1; return cnt; } void printKAlmostPrimes(int k, int n) { //Your code here int i,num; for(i=1,num=2;i<=n;num++) { if(CountOfPrime(num)==k) { printf("%d ",num); i++; } } } |
11827
|
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 |
#include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <vector> using namespace std; vector<int> vb; int gcd(int a,int b) { if(a%b==0) return b; else return gcd(b,a%b); } int main() { int n,a; int x,y; string str; cin>>n; getchar(); stringstream iss; int mx; while(n--) { //cin>>x>>y; //cout<<gcd(x,y)<<"\n"; getline(cin,str); iss<<str; mx=0; vb.clear(); while(iss>>a) { //cout<<"sdd\n"; vb.push_back(a); } iss.clear(); for(int i=0;i<vb.size()-1;i++) { for(int j=i+1;j<vb.size();j++) { a = gcd(vb[i],vb[j]); if(a>mx) mx = a; } } printf("%d\n",mx); } return 0; } |
10223
|
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 |
#include <iostream> #include <cstdio> #define ll long long using namespace std; ll catalan[25]; ll findcatalan(int n) { ll res = 1; int lim; for(int i=n+2;i<=2*n;i++) { if(i%2==0) res*=2; else res*=i; } if((n+2)%2==0) lim = (n+2)/2; else lim = (n+3)/2; for(int i=2;i<lim;i++) { res/=i; } return res; } int binSearch(ll num) { int lw=0,hi=17; int mid; /*while(lw<hi) { mid=lw+(hi-lw)/2; if(catalan[mid]<num) lw = mid+1; else if(catalan[mid]==num) return mid; else if(catalan[mid]>num) hi = mid; }*/ for(int i=1;i<20;i++) { if(num==catalan[i]) return i; } return 0; } int main() { catalan[0]=1; catalan[1]=1; catalan[2]=2; ll num; int idx; for(int i=3;i<20;i++) { catalan[i] = findcatalan(i); } while(cin>>num) { idx = binSearch(num); cout<<idx<<"\n"; } return 0; } |
1225
|
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 |
#include <iostream> #include <cstdio> #include <vector> #include <queue> #include <sstream> #include <string> #include <cstring> #include <cmath> #define ll long long using namespace std; ll digitCount[10]; ll pwr; ll numberOfDigit[15];//total count of i digit numbers int getLength(int a) { if(a<10) { pwr=1; return 1; } int len=0; pwr=1; while(a) { len+=1; a/=10; pwr*=10; } pwr/=10;//10 to the powr length-1; i.e for 3 digit number 10^2=100 return len; } int main() { int t,n,msd,length; ll totaldigit,leadingZeros,nonzeros; numberOfDigit[0]=0; numberOfDigit[1]=9;//there are 9 1'digit numbers, 90 2'digit numbers for(int i=2;i<15;i++) numberOfDigit[i]=numberOfDigit[i-1]*10; scanf("%d",&t); while(t--) { scanf("%d",&n); leadingZeros=0; nonzeros=0; for(int i=0;i<10;i++) digitCount[i]=0; length = getLength(n); for(int i=1;i<length;i++) { leadingZeros+= numberOfDigit[i]*(length-i); } totaldigit = length*n;//including leading and trailing zeros while(n) { msd = n/pwr; for(int i=1;i<10;i++) { digitCount[i]+= msd*(length-1)*(pwr/10);//N*10^(N-1) each digit, here N = length-1 and pwr/10 = 10^(N-1) } for(int i=1;i<msd;i++) digitCount[i]+=pwr; digitCount[msd]+=(n%pwr+1); n=n%pwr; pwr/=10; length-=1; } for(int i=1;i<10;i++) nonzeros+=digitCount[i]; digitCount[0] = totaldigit-leadingZeros-nonzeros; for(int i=0;i<10;i++) cout<<digitCount[i]<<(i!=9?" ":"\n"); } return 0; } |
11970
|
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 |
#include <iostream> #include <cstdio> #include <queue> #include <sstream> #include <string> #include <vector> #include <cstring> #include <cmath> #define ll long long using namespace std; vector<ll> v; int main() { int t; ll n,sq,sq_root,x; int kase=1; scanf("%d",&t); while(t--) { scanf("%lld",&n); sq=0; int k=0; v.clear(); for(ll i=0;;i++) { sq += 2*i+1; sq_root=i+1; if(sq>=n) break; x = n-sq; if(x%sq_root==0 && x!=0) v.push_back(x); } printf("Case %d:",kase++); for(int i=v.size()-1;i>=0;i--) printf(" %lld",v[i]); printf("\n"); } return 0; } |
11121
|
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 |
#include <iostream> #include <cstdio> #include <cstdio> #include <cstring> #include <string> #include <vector> #include <cmath> #include <cstdlib> #define INF 1000000 #define ll long long using namespace std; int main() { int t,kase=1; ll n; int a=-2,b=-3; //cout<<a%2<<" "<<b%2<<"\n"; string str; scanf("%d",&t); while(t--) { scanf("%lld",&n); if(n==0) { printf("Case #%d: ",kase++); printf("0\n"); continue; } str=""; while(n) { if(n%2) { //cout<<"got\n"; str.append(1u,'1'); n -= 1;n/=(-2); } else { n/=(-2); //if(str.size()) str.append(1u,'0'); } } printf("Case #%d: ",kase++); for(int i=str.size()-1;i>=0;i--) printf("%c",str[i]); printf("\n"); } return 0; } |
12459
|
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 |
#include <iostream> #include <cstdio> #include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <cstdlib> #include <fstream> #define INF 1000000 #define ll long long using namespace std; struct node{ ll female,male,sum; }; int main() { node fib[85]; fib[1].female=0; fib[1].male=1; fib[1].sum=1; fib[2].female=1; fib[2].male=1; fib[2].sum=2; for(int i=3;i<85;i++) { fib[i].female=fib[i-1].sum; fib[i].male=fib[i-1].female; fib[i].sum=fib[i].male+fib[i].female; } int n; while(scanf("%d",&n)) { if(n==0) break; printf("%lld\n",fib[n].sum); } return 0; } |
11466
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; } |
10533
|
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 |
#include <iostream> #include <cstdio> #include <sstream> #include <string> using namespace std; bool prime[1000001]; bool firstPrime[1000001]; int primeCount[1000001]; bool checkdigit(int a) { int sum; if(a<10) return 1; else { sum=0; while(a) { sum+=a%10; a/=10; } if(firstPrime[sum]==0) return 1; else return 0; } return 0; } int main() { int cnt=0; prime[0]=1; prime[1]=1; firstPrime[0]=1; firstPrime[1]=1; primeCount[0]=cnt; primeCount[1]=cnt; for(int i=2;i<1000001;i++) { if(prime[i]==0) { if(!checkdigit(i)) prime[i]=1; else { cnt+=1; } for(int j=i+i;j<1000001;j+=i) { prime[j]=1; firstPrime[j]=1; } } primeCount[i]=cnt; } int t,a,b,add; scanf("%d",&t); while(t--) { add=0; scanf("%d%d",&a,&b); if(firstPrime[a]==0 && checkdigit(a)) add=1; printf("%d\n",primeCount[b]-primeCount[a]+add); } return 0; } |