Prime – Live with passion

Almost Prime number

Asif NaeemSeptember 24, 2016

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;
    
    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++;
        }
    }
}

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++;

}

11466

Asif NaeemJuly 28, 2015

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 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;
}

#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;

}

1644

Asif NaeemMay 2, 2015

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;

int n;
int arr[1300000];
vector<int> v;

int main()
{
	int lo,hi,mid;
	for(int i=0;i<1300000;i++)
	{
		arr[i]=0;
	}

	for(int i=2;i<sqrt(1300000);i++)
	{
		if(arr[i]==0)
		{
			for(int j=i+i;j<1300000;j+=i)
			{
				arr[j]=1;
			}
		}
	}

	for(int i=2;i<1300000;i++)
	{
		if(arr[i]==0)
		{
			v.push_back(i);
		}
	}
	//cout<<v.size()<<"\n";
	while(scanf("%d",&n),n)
	{
		if(arr[n]==0)
		{
			cout<<0<<"\n";
			continue;
		}
		lo=0;hi=v.size()-1;
		while(hi-lo>1)
		{
			if((hi-lo)%2)
			{
				mid=lo+(hi-lo)/2+1;
			}
			else
				mid=lo+(hi-lo)/2;
			//cout<<lo<<" "<<mid<<" "<<hi<<" "<<n<<"\n";
			//getchar();
			if(n<v[mid])
			{
				hi=mid;
			}
			else
			{
				lo=mid;
			}
		}
		cout<<v[hi]-v[lo]<<"\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cmath>

#include <vector>

using namespace std;

int n;

int arr[1300000];

vector<int> v;

int main()

{

int lo,hi,mid;

for(int i=0;i<1300000;i++)

{

arr[i]=0;

}

for(int i=2;i<sqrt(1300000);i++)

{

if(arr[i]==0)

{

for(int j=i+i;j<1300000;j+=i)

{

arr[j]=1;

}

for(int i=2;i<1300000;i++)

{

if(arr[i]==0)

{

v.push_back(i);

}

//cout<<v.size()<<"\n";

while(scanf("%d",&n),n)

{

if(arr[n]==0)

{

cout<<0<<"\n";

continue;

}

lo=0;hi=v.size()-1;

while(hi-lo>1)

{

if((hi-lo)%2)

{

mid=lo+(hi-lo)/2+1;

}

else

mid=lo+(hi-lo)/2;

//cout<<lo<<" "<<mid<<" "<<hi<<" "<<n<<"\n";

//getchar();

if(n<v[mid])

{

hi=mid;

}

else

{

lo=mid;

}

cout<<v[hi]-v[lo]<<"\n";

}

return 0;

}

12542

Asif NaeemNovember 19, 2014

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <math.h>
#include <vector>

#define SZ 100005

using namespace std;

int prim[SZ];
vector<int> v;

void primgen()
{
	v.push_back(2);
	prim[2]=0;
	for(int i=3;i<SZ;i+=2)
	{
		if(prim[i]==0)
		{
			v.push_back(i);
			for(int j=i*3;j<SZ;j+=i)
			prim[j]=1;
		}
	}

	//cout<<v.size()<<"\n";
}

int main()
{
	int mult[5];
	int m,max_;
	string s;
	primgen();

	while(cin>>s)
	{
		if(s=="0")
		break;
		memset(mult,0,sizeof(mult));
		max_=0;
		m=0;
		for(int j=0;j<s.size();j++)
		{
			m=0;
			//max_=0;
			for(int k=j;k<j+5;k++)
			{
				if(k==s.size())
				break;
				m*=10;
				m+=(s[k]-'0');

				if(m==2 || (prim[m]==0 && m%2==1))
				{
					if(m>max_)
					max_=m;
				}
			}
		}//
		cout<<max_<<"\n";
	}

	return 0;
}

#include <stdio.h>

#include <string.h>

#include <string>

#include <iostream>

#include <math.h>

#include <vector>

#define SZ 100005

using namespace std;

int prim[SZ];

vector<int> v;

void primgen()

{

v.push_back(2);

prim[2]=0;

for(int i=3;i<SZ;i+=2)

{

if(prim[i]==0)

{

v.push_back(i);

for(int j=i*3;j<SZ;j+=i)

prim[j]=1;

}

//cout<<v.size()<<"\n";

}

int main()

{

int mult[5];

int m,max_;

string s;

primgen();

while(cin>>s)

{

if(s=="0")

break;

memset(mult,0,sizeof(mult));

max_=0;

m=0;

for(int j=0;j<s.size();j++)

{

m=0;

//max_=0;

for(int k=j;k<j+5;k++)

{

if(k==s.size())

break;

m*=10;

m+=(s[k]-'0');

if(m==2 || (prim[m]==0 && m%2==1))

{

if(m>max_)

max_=m;

}

}//

cout<<max_<<"\n";

}

return 0;

}

10780

Asif NaeemNovember 16, 2014

#include <iostream>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <fstream>

#define ull  unsigned long long

using namespace std;


int factor[10001][1230];
int factorcount[10001][1230];
int prime[10001];
vector<int> v;
ull _MAX;

void primegenerator()
{
	double p=sqrt(10001);

	v.push_back(2);

	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		for(int j=i*i;j<10001;j+=i)
			prime[j]=1;
	}

	for(int i=3;i<10001;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}

}

void factorize()
{
	for(int i=2;i<10001;i++)
	{
		int tmp=i;
		int j=0;
		while(tmp>1)
		{
			if(tmp%v[j]==0)
			{
				factorcount[i][j]++;
				factor[i][j]++;
				tmp/=v[j];
				j=-1;

			}
			j++;
			if(j==v.size())
			break;
		}
		for(int k=0;k<1230;k++)
		factorcount[i][k]+=factorcount[i-1][k];

	}
}

int main()
{
	primegenerator();
	factorize();
	int t,m,n;
	int kase=0;
	cin>>t;
	while(t--)
	{
		cin>>m>>n;
		kase+=1;
		if(m<=1 || n<=0)
		{
			cout<<"Case "<<kase<<":\n";
			cout<<"Impossible to divide\n";
			continue;
		}
		int imposbl=0;
		double min_d=2e9;
		for(int i=0;i<1230;i++)
		{
			if(factor[m][i]>factorcount[n][i])
			{
				imposbl=1;
				break;
			}
			else if(factor[m][i] && factorcount[n][i] && factorcount[n][i]/factor[m][i] <min_d)
			{
                 min_d = factorcount[n][i]/factor[m][i];
			}
		}
		cout<<"Case "<<kase<<":\n";
		if(imposbl==1)
		{
           cout<<"Impossible to divide\n";
        }
		else
		{
            cout<<min_d<<"\n";
        }

	}


	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <cstring>

#include <math.h>

#include <stdio.h>

#include <vector>

#include <fstream>

#define ull unsigned long long

using namespace std;

int factor[10001][1230];

int factorcount[10001][1230];

int prime[10001];

vector<int> v;

ull _MAX;

void primegenerator()

{

double p=sqrt(10001);

v.push_back(2);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

for(int j=i*i;j<10001;j+=i)

prime[j]=1;

}

for(int i=3;i<10001;i+=2)

{

if(prime[i]==0)

v.push_back(i);

}

void factorize()

{

for(int i=2;i<10001;i++)

{

int tmp=i;

int j=0;

while(tmp>1)

{

if(tmp%v[j]==0)

{

factorcount[i][j]++;

factor[i][j]++;

tmp/=v[j];

j=-1;

}

j++;

if(j==v.size())

break;

}

for(int k=0;k<1230;k++)

factorcount[i][k]+=factorcount[i-1][k];

}

int main()

{

primegenerator();

factorize();

int t,m,n;

int kase=0;

cin>>t;

while(t--)

{

cin>>m>>n;

kase+=1;

if(m<=1 || n<=0)

{

cout<<"Case "<<kase<<":\n";

cout<<"Impossible to divide\n";

continue;

}

int imposbl=0;

double min_d=2e9;

for(int i=0;i<1230;i++)

{

if(factor[m][i]>factorcount[n][i])

{

imposbl=1;

break;

}

else if(factor[m][i] && factorcount[n][i] && factorcount[n][i]/factor[m][i] <min_d)

{

min_d = factorcount[n][i]/factor[m][i];

}

cout<<"Case "<<kase<<":\n";

if(imposbl==1)

{

cout<<"Impossible to divide\n";

}

else

{

cout<<min_d<<"\n";

}

return 0;

}

10394

Asif NaeemNovember 16, 2014

#include <iostream>
#include <string>
#include <vector>
#include <math.h>

#define SZ 20000001

using namespace std;

int prime[SZ];
vector<int> v;

struct twin{
	int x;
	int y;
}twinPrime[108001];

void primegen()
{
	double p = sqrt(SZ);

	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		{
			for(int j=i*i;j<SZ;j+=i)
				prime[j]=1;
		}
	}

	v.push_back(2);
	int cnt=0;
	for(int i=3;i<SZ;i+=2)
	{
		if(prime[i]==0)
		{
			v.push_back(i);
			int t=v.size();
			if(v[t-1]-v[t-2]==2)
			{
				twinPrime[cnt].x = v[t-2];
				twinPrime[cnt].y = v[t-1];
				cnt++;
			}
		}
	}
}


int main()
{
	primegen();
	int size = v.size();
	int n;

	while(cin>>n)
	{
		cout<<"("<<twinPrime[n-1].x<<", "<<twinPrime[n-1].y<<")\n";
	}
	return 0;
}

#include <iostream>

#include <string>

#include <vector>

#include <math.h>

#define SZ 20000001

using namespace std;

int prime[SZ];

vector<int> v;

struct twin{

int x;

int y;

}twinPrime[108001];

void primegen()

{

double p = sqrt(SZ);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

{

for(int j=i*i;j<SZ;j+=i)

prime[j]=1;

}

v.push_back(2);

int cnt=0;

for(int i=3;i<SZ;i+=2)

{

if(prime[i]==0)

{

v.push_back(i);

int t=v.size();

if(v[t-1]-v[t-2]==2)

{

twinPrime[cnt].x = v[t-2];

twinPrime[cnt].y = v[t-1];

cnt++;

}

int main()

{

primegen();

int size = v.size();

int n;

while(cin>>n)

{

cout<<"("<<twinPrime[n-1].x<<", "<<twinPrime[n-1].y<<")\n";

}

return 0;

}

11347

Asif NaeemNovember 14, 2014

#include <iostream>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <vector>

#define ull  unsigned long long
#define max(a,b) a>=b?a:b

using namespace std;

int ans[200];
int prime[1001];
vector<int> v;
ull _MAX;

void primegenerator()
{
	double p=sqrt(1001);

	v.push_back(2);

	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		for(int j=i*2;j<1001;j+=i)
			prime[j]=1;
	}

	for(int i=3;i<1001;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}

}

int main()
{
	string s;
	int _max=0;
	int t,cnt,num;
	int kase=1;
	_MAX = 1000000000;
	_MAX *=_MAX;
	primegenerator();
	cout<<v.size()<<"\n";
	cin>>t;

	while(t--)
	{
		cin>>s;
		cnt=0;
		num=0;
		_max=0;
		memset(ans,0,sizeof(ans));
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='!')
			cnt++;
			else
			{
				num*=10;
				num+=(s[i]-'0');
			}
		}
		//cout<<num<<" "<<cnt<<"\n";
		cout<<"Case "<<kase++<<": ";

		while(num>1)
		{
			int tmp=num;
			int j=0;
			while(tmp>1)
			{
				if(tmp%v[j]==0)
				{
					tmp/=v[j];
					ans[j]++;
					//_max=max(j,_max);

				}
				else
				j++;
			}
			num-=cnt;
		}

		ull res=1;
		int f=1;
		for(int i=0;i<v.size();i++)
		{
			if(ans[i]!=0)
			res*=(ans[i]+1);
			if(res>_MAX)
			{
				f=0;
				break;
			}
		}
		if(f==1)
		cout<<res<<"\n";
		else
		cout<<"Infinity\n";
	}
	return 0;
}

100

101

102

103

104

105

106

107

#include <iostream>

#include <cstring>

#include <math.h>

#include <stdio.h>

#include <vector>

#define ull unsigned long long

#define max(a,b) a>=b?a:b

using namespace std;

int ans[200];

int prime[1001];

vector<int> v;

ull _MAX;

void primegenerator()

{

double p=sqrt(1001);

v.push_back(2);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

for(int j=i*2;j<1001;j+=i)

prime[j]=1;

}

for(int i=3;i<1001;i+=2)

{

if(prime[i]==0)

v.push_back(i);

}

int main()

{

string s;

int _max=0;

int t,cnt,num;

int kase=1;

_MAX = 1000000000;

_MAX *=_MAX;

primegenerator();

cout<<v.size()<<"\n";

cin>>t;

while(t--)

{

cin>>s;

cnt=0;

num=0;

_max=0;

memset(ans,0,sizeof(ans));

for(int i=0;i<s.size();i++)

{

if(s[i]=='!')

cnt++;

else

{

num*=10;

num+=(s[i]-'0');

}

//cout<<num<<" "<<cnt<<"\n";

cout<<"Case "<<kase++<<": ";

while(num>1)

{

int tmp=num;

int j=0;

while(tmp>1)

{

if(tmp%v[j]==0)

{

tmp/=v[j];

ans[j]++;

//_max=max(j,_max);

}

else

j++;

}

num-=cnt;

}

ull res=1;

int f=1;

for(int i=0;i<v.size();i++)

{

if(ans[i]!=0)

res*=(ans[i]+1);

if(res>_MAX)

{

f=0;

break;

}

if(f==1)

cout<<res<<"\n";

else

cout<<"Infinity\n";

}

return 0;

}

11415

Asif NaeemNovember 12, 2014

#include <iostream>
#include <math.h>
#include <vector>

#define ull unsigned long long
#define SIZE 2703664
using namespace std;

int prime[1700];//3200
ull factor[SIZE];
int arr[10000001];
vector<int> v;

void primeGenerator()
{
	double p = sqrt(1700);
	for(int i=3;i<p;i+=2)
	{
		if(prime[i]==0)
		{
			for(int j=i+i;j<1700;j+=i)
			prime[j]=1;
		}
	}

	v.push_back(2);

	for(int i=3;i<1700;i+=2)
	{
		if(prime[i]==0)
		v.push_back(i);
	}
}


void countfactor()
{
	int tmp;
	factor[0]=1;

	factor[1]=1;

	factor[2]=1;


	for(int i=3;i<SIZE;i++)
	{
		tmp = i;
		int j=0;
		factor[i]=0;
		while(tmp>=(v[j]*v[j]))
		{
			if(tmp%v[j]==0)
			{
				tmp/=v[j];
				factor[i]++;
				j=-1;
			}
			j++;

			if(j==v.size())
			break;

		}
		if(tmp>1)
		factor[i]++;

		factor[i]+=factor[i-1];


	}

}

int main()
{
	primeGenerator();
	countfactor();

	ull low,mid,high;
	ull n,ans=0;
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		low=0;
		mid=SIZE/2;
		high=SIZE;
		ans = 0;
		if(arr[n])
		{
			cout<<arr[n]<<"\n";
			continue;
		}
		while((high-low)>1)
		{
			if(factor[mid]<=n)
			{
				low=mid;
				mid=(low+high)/2;
				//ans=high;
			}
			else
			{
				high=mid;
				mid=(low+high)/2;
				//ans=low;
			}
		}

		if(factor[mid+1]>n && factor[mid]<=n)
		{
			arr[n]=mid+1;
		}
		cout<<arr[n]<<"\n";
	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

#include <iostream>

#include <math.h>

#include <vector>

#define ull unsigned long long

#define SIZE 2703664

using namespace std;

int prime[1700];//3200

ull factor[SIZE];

int arr[10000001];

vector<int> v;

void primeGenerator()

{

double p = sqrt(1700);

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

{

for(int j=i+i;j<1700;j+=i)

prime[j]=1;

}

v.push_back(2);

for(int i=3;i<1700;i+=2)

{

if(prime[i]==0)

v.push_back(i);

}

void countfactor()

{

int tmp;

factor[0]=1;

factor[1]=1;

factor[2]=1;

for(int i=3;i<SIZE;i++)

{

tmp = i;

int j=0;

factor[i]=0;

while(tmp>=(v[j]*v[j]))

{

if(tmp%v[j]==0)

{

tmp/=v[j];

factor[i]++;

j=-1;

}

j++;

if(j==v.size())

break;

}

if(tmp>1)

factor[i]++;

factor[i]+=factor[i-1];

}

int main()

{

primeGenerator();

countfactor();

ull low,mid,high;

ull n,ans=0;

int t;

cin>>t;

while(t--)

{

cin>>n;

low=0;

mid=SIZE/2;

high=SIZE;

ans = 0;

if(arr[n])

{

cout<<arr[n]<<"\n";

continue;

}

while((high-low)>1)

{

if(factor[mid]<=n)

{

low=mid;

mid=(low+high)/2;

//ans=high;

}

else

{

high=mid;

mid=(low+high)/2;

//ans=low;

}

if(factor[mid+1]>n && factor[mid]<=n)

{

arr[n]=mid+1;

}

cout<<arr[n]<<"\n";

}

return 0;

}

10856

Asif NaeemNovember 9, 2014

#include <iostream>
#include <string>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <stdlib.h>

#define SIZE 2800001
#define ull unsigned long long

using namespace std;

int prime[1700];
ull arr [SIZE];//[10000001+5];
vector<int> v;

void primeGenerator()
{
	double p = sqrt(1700);
	for(int i=3;i<p;i+=2)
	{
		for(int j=i+i;j<1700;j+=i)
		{
			prime[j]=1;
		}
	}

	v.push_back(2);

	for(int i=3;i<1700;i++)
	{
		if(prime[i]==0 && i%2!=0)
		{
			v.push_back(i);
		}
	}
}

void factorize()
{
	int tmp;
	arr[0]=1;
	arr[1]=0;
	arr[2]=1;
	for(int i=3;i<SIZE;i++)
	{
		tmp = i;
		arr[i]=0;
		int j=0;
		while(tmp>=(v[j]*v[j]))
		{
			if(tmp%v[j]==0)
			{
				tmp/=v[j];
				arr[i]++;
				j=-1;
			}
			j++;

			if(j==v.size())
			break;
		}
		//cout<<tmp<<"\n";
		if(tmp>1)
		 arr[i]++;
		arr[i]+=arr[i-1];
	}
}

int main()
{
	int n,kase=1;
	int mid;
	int high;
	int low;
	for(int i=0;i<1700;i++)
	{
		prime[i]=0;
	}
	primeGenerator();
	factorize();
	while(cin>>n)
	{
		if(n<0)
		break;
		if(n==0)
		{
			cout<<"Case "<<kase++<<": 0!\n";
			continue;

		}
		mid=SIZE/2;
		high=SIZE;
		low=0;

		//binary search
		while((high-low)>1)
		{
			mid=(high+low)/2;
			if(arr[mid]<n)
				low=mid;
			else
				high = mid;

		}
		if(arr[low]==n)
		cout<<"Case "<<kase++<<": "<<low<<"!\n";
		else if(arr[high]==n)
		cout<<"Case "<<kase++<<": "<<high<<"!\n";
		else
		cout<<"Case "<<kase++<<": Not possible.\n";

	}

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include <iostream>

#include <string>

#include <stdio.h>

#include <math.h>

#include <vector>

#include <stdlib.h>

#define SIZE 2800001

#define ull unsigned long long

using namespace std;

int prime[1700];

ull arr [SIZE];//[10000001+5];

vector<int> v;

void primeGenerator()

{

double p = sqrt(1700);

for(int i=3;i<p;i+=2)

{

for(int j=i+i;j<1700;j+=i)

{

prime[j]=1;

}

v.push_back(2);

for(int i=3;i<1700;i++)

{

if(prime[i]==0 && i%2!=0)

{

v.push_back(i);

}

void factorize()

{

int tmp;

arr[0]=1;

arr[1]=0;

arr[2]=1;

for(int i=3;i<SIZE;i++)

{

tmp = i;

arr[i]=0;

int j=0;

while(tmp>=(v[j]*v[j]))

{

if(tmp%v[j]==0)

{

tmp/=v[j];

arr[i]++;

j=-1;

}

j++;

if(j==v.size())

break;

}

//cout<<tmp<<"\n";

if(tmp>1)

arr[i]++;

arr[i]+=arr[i-1];

}

int main()

{

int n,kase=1;

int mid;

int high;

int low;

for(int i=0;i<1700;i++)

{

prime[i]=0;

}

primeGenerator();

factorize();

while(cin>>n)

{

if(n<0)

break;

if(n==0)

{

cout<<"Case "<<kase++<<": 0!\n";

continue;

}

mid=SIZE/2;

high=SIZE;

low=0;

//binary search

while((high-low)>1)

{

mid=(high+low)/2;

if(arr[mid]<n)

low=mid;

else

high = mid;

}

if(arr[low]==n)

cout<<"Case "<<kase++<<": "<<low<<"!\n";

else if(arr[high]==n)

cout<<"Case "<<kase++<<": "<<high<<"!\n";

else

cout<<"Case "<<kase++<<": Not possible.\n";

}

return 0;

}

10139

Asif NaeemNovember 8, 2014

#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <sstream>
#include <fstream>

#define SIZE 46500
#define lld long long
using namespace std;

// sqrt of 2^31 is ~46400
vector<int> v;
int prime[SIZE];

void PrimeGenerate()
{
    double p = sqrt(SIZE)+4;

    for(int i=3;i<p;i+=2)
    {
        if(prime[i]==0)
        {
            for(int j=i+i;j<SIZE;j+=i)
            prime[j]=1;

        }
    }
    v.clear();
    v.push_back(2);

    for(int j=3;j<SIZE;j++)
    {
       if(prime[j]==0 && j%2!=0)
       v.push_back(j);
    }

}

int main()
{
  int m,cnt;
  lld a,n;
  map<int,int> mp;
  PrimeGenerate();
  //cout<<prime[21471]<<"\n";
  //ofstream out;
  //out.open("out.txt");

  while(cin>>n)
  {
     cin>>m;
     //if(m==0 && n==0)
     //break;
     cnt=0;
     if(n>=m)
     {
        cout<<m<<" divides "<<n<<"!\n";
        //out<<m<<" divides "<<n<<"!\n";
        continue;
     }
     mp.clear();
     lld tmp = m;
     int j=0;
     int f=0;
     while(tmp>=v[j]*v[j])
     {
         if(tmp%v[j]==0)
         {
            tmp/=v[j];
            if(v[j]>n)
            {
               f=1;
               break;
            }
            mp[v[j]]++;
            cnt++;
            j=-1;
         }
         j++;
         if(j==v.size())
         break;
     }
     if(f)
     {
       //cout<<"1)\n";
       cout<<m<<" does not divide "<<n<<"!\n";
       //out<<m<<" does not divide "<<n<<"!\n";
       continue;
     }
     if(tmp>1)
     {
       if(tmp>n)
       {
         //cout<<"2)\n";
         cout<<m<<" does not divide "<<n<<"!\n";
         //out<<m<<" does not divide "<<n<<"!\n";
         continue;
       }
       mp[tmp]++;
       cnt++;
     }
     //cout<<mp.size()<<"\n";
     for(map<int,int>::iterator ii=mp.begin();ii!=mp.end();++ii)
     {
         a = 1;//ii->first;
         int t=0;//=n/a;
         int add=0;
         //cout<<t<<" "<<a<<" "<<n<<"\n";
         while(1)
         {
             a*=ii->first;
             add=n/a;
             t+=add;
             if(add==0)
             break;

         }
         if(t<ii->second)
         {
            f=1;
            break;
         }

         //cout<<ii->first<<" "<<ii->second<<"\n";
     }
     if(f)
     {
       //cout<<"3)\n";
       cout<<m<<" does not divide "<<n<<"!\n";
       //out<<m<<" does not divide "<<n<<"!\n";
     }
     else
     {
       cout<<m<<" divides "<<n<<"!\n";
       //out<<m<<" divides "<<n<<"!\n";
     }
  }
  //out.close();
  return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

#include <iostream>

#include <math.h>

#include <vector>

#include <map>

#include <sstream>

#include <fstream>

#define SIZE 46500

#define lld long long

using namespace std;

// sqrt of 2^31 is ~46400

vector<int> v;

int prime[SIZE];

void PrimeGenerate()

{

double p = sqrt(SIZE)+4;

for(int i=3;i<p;i+=2)

{

if(prime[i]==0)

{

for(int j=i+i;j<SIZE;j+=i)

prime[j]=1;

}

v.clear();

v.push_back(2);

for(int j=3;j<SIZE;j++)

{

if(prime[j]==0 && j%2!=0)

v.push_back(j);

}

int main()

{

int m,cnt;

lld a,n;

map<int,int> mp;

PrimeGenerate();

//cout<<prime[21471]<<"\n";

//ofstream out;

//out.open("out.txt");

while(cin>>n)

{

cin>>m;

//if(m==0 && n==0)

//break;

cnt=0;

if(n>=m)

{

cout<<m<<" divides "<<n<<"!\n";

//out<<m<<" divides "<<n<<"!\n";

continue;

}

mp.clear();

lld tmp = m;

int j=0;

int f=0;

while(tmp>=v[j]*v[j])

{

if(tmp%v[j]==0)

{

tmp/=v[j];

if(v[j]>n)

{

f=1;

break;

}

mp[v[j]]++;

cnt++;

j=-1;

}

j++;

if(j==v.size())

break;

}

if(f)

{

//cout<<"1)\n";

cout<<m<<" does not divide "<<n<<"!\n";

//out<<m<<" does not divide "<<n<<"!\n";

continue;

}

if(tmp>1)

{

if(tmp>n)

{

//cout<<"2)\n";

cout<<m<<" does not divide "<<n<<"!\n";

//out<<m<<" does not divide "<<n<<"!\n";

continue;

}

mp[tmp]++;

cnt++;

}

//cout<<mp.size()<<"\n";

for(map<int,int>::iterator ii=mp.begin();ii!=mp.end();++ii)

{

a = 1;//ii->first;

int t=0;//=n/a;

int add=0;

//cout<<t<<" "<<a<<" "<<n<<"\n";

while(1)

{

a*=ii->first;

add=n/a;

t+=add;

if(add==0)

break;

}

if(t<ii->second)

{

f=1;

break;

}

//cout<<ii->first<<" "<<ii->second<<"\n";

}

if(f)

{

//cout<<"3)\n";

cout<<m<<" does not divide "<<n<<"!\n";

//out<<m<<" does not divide "<<n<<"!\n";

}

else

{

cout<<m<<" divides "<<n<<"!\n";

//out<<m<<" divides "<<n<<"!\n";

}

//out.close();

return 0;

}

Category: Prime

Almost Prime number

11466

1644

12542

10780

10394

11347

11415

10856

10139

Archives

Categories