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 /*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;
11827
#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); }
10223
#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;
1225
#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
11970
#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
11121
#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)
12459
#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;
11466
There should be a better approach to improve the time complexity. #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
10533
#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;