so apply sieve of eratosthenes...????

Moderator: Board moderators
So, you think a problem which is !(specific & simple),that is challenging?moonstruck wrote:If the problem is simple & specific, then where is our challenges?
Code: Select all
#include<stdio.h>
#include<math.h>
#define MAX 2000000
#define PRIME 0
#define NOTPRIME 1
unsigned char flag[MAX];
void seive()
{
int i,j,sq;
flag[0]=flag[1]=NOTPRIME;
flag[2] = PRIME;
sq = (int) sqrt(MAX);
for (i = 4; i < MAX; i += 2)
flag[i] = NOTPRIME;
for(i = 3; i < sq; i+= 2)
{
if(flag[i] == PRIME)
{
for(j = i*i; j < MAX; j+= i)
{
flag[j] = NOTPRIME;
}
}
}
}
int main()
{
int N,Nn,i,count,sq;
seive();
while(scanf("%d",&N)!=EOF)
{
count = 0;
while(N--)
{
scanf("%d",&Nn);
sq = sqrt(Nn);
if(flag[Nn] == NOTPRIME)
{
for(i=2;i<=sq;i++)
{
if(flag[i] == PRIME && Nn%i == 0 && flag[Nn/i] == PRIME)
{
count++;
break;
}
}
}
}
printf("%d\n",count);
}
return 0;
}
Code: Select all
5
999997 999998 999999 1000000 1000001
Code: Select all
2
Code: Select all
#include<stdio.h>
#define MAX 1048580
bool isnp[MAX+3],cp[MAX+3];
int main()
{
long int i,j,p,n,c,flag,b,x;
isnp[1]=isnp[0]=true;
for(i=2;i*i<=MAX;i++)
{
if(!isnp[i])
{
for(j=i*i;j<=MAX;j+=i)
isnp[j]=true;
}
}
while(scanf("%ld",&n)==1)
{
x=0;
for(i=0;i<n;i++)
{
scanf("%ld",&b);
if(b==0 || b==1)
cp[b]=false;
else if(isnp[b]==false)
{
cp[b]=false;
}
else
{
flag=0;
for(j=2;(j*j)<=b;j++)
{
c=0;
if(b%j==0)
{
p=b/j;
c=1;
}
if(c==1 && (isnp[j]==true || isnp[p]==true))
{
flag=1;
break;
}
}
if(flag==1)
cp[b]=false;
else
cp[b]=true;
}
if(cp[b]==true)
x++;
}
printf("%ld\n",x);
}
return 0;
}