OJ Board

Code: Select all

the condition i<SIZE
into:
i<= sqrt(SIZE)

Code: Select all

#include<stdio.h>
#include<math.h>

#define SIZE 1000001

long  a,b,data[SIZE]={0},add[SIZE]={0};


void s (void);
long sum_prime(void);


int main()
{
	long k,i,result,cas,sum=0,z,dum,m;
	s();
	sum=0;
	for(i=0;i<SIZE;i++)
	{
		if(!data[i])
		{
			z=i;dum=0;
			while(z)
			{
				m=z%10;
				dum +=m;
				z /=10;
			}
			if(!data[dum])
			{
				sum++;
				add[i]=sum;
			}
		}
		else
			add[i]=sum;
	}
	scanf("%ld",&cas);
	for(k=1;k<=cas;k++)
	{
		scanf("%ld %ld",&a, &b);
		result=sum_prime();
		printf("%ld\n",result);
	}
	return 0;
}



void s(void)
{
	long i,j,sqrtNum;
	data[0]=1;
	data[1]=1;
	for(i=4;i<SIZE;i+=2)
		data[i]=1;
	sqrtNum = (long)sqrt(SIZE);
	for(i=3;i<sqrtNum;i+=2)
		for(j=i;i*j<SIZE;j++)
			if(!data[i*j])
				data[i*j]=1;
}



long sum_prime(void)
{
	long XX,z,dum,m;
	if(a!=b)
		XX=add[b]-add[a];
	else if(a==b)
	{
		if(!data[a])
		{
			dum=0;z=a;
			while(z)
			{
				m=z%10;
				dum +=m;
				z /=10;
			}
			if(!data[dum])
				XX=1;
		}
		else
			XX=0;
	}
	return XX;
}

Code: Select all

What if you use add[b] - add[a-1] ?

Code: Select all

            1  2  3  4  5  6  7  8  9  10
            |  |  |  |  |  |  |  |  |  |
            N  P  P  N  P  N  P  N  N  N

Code: Select all

     N-> Not prime
     P-> Prime & have prime digit

Code: Select all

            1  2  3  4  5  6  7  8  9  10
            |  |  |  |  |  |  |  |  |  |
            N  P  P  N  P  N  P  N  N  N
     add[]->0  1  2  2  3  3  4  4  4  4

Code: Select all

Question: Find the total answer from 5th[a] element to 10th[b] element?
answer:  add[b-1] - add[a-1] that is 
         add[9] - add[4]

Code: Select all

Question: Find the total answer from 4th[a] element to 4th[b] element?

answer: First i have checked if the 4th element is prime and have prime digit then i printed 1 otherwise 0;  

Code: Select all

#include<iostream>
#include<cstdio>

using namespace std;

#define SIZE 1000002

long  a,b,i,j;
char data[SIZE]={0};
int dp[SIZE];
int nop[SIZE];
void sieve(void)
{
   int i, j, k;

   data[0] = 1;
   data[1] = 1;

   for (i=4; i<SIZE; i+=2)
   {
      data[i] = 1;
   }

   for (i=3; i<SIZE; i+=2)
   {
      if (!data[i])
      {
         k = SIZE / i;
      
         for (j=i; j<=k; j+=2)
         {
            data[i * j] = 1;
         }
      }

   
   }
}
void is_dp()
{
	long x,z,ct=0,du,m=0;
	for(i=0;i<SIZE;i++)
	{
		if(!data[i])
		{
			z=x=i;
			du=0;
			while(z)
			{
				m=z%10;
				du+=m;
				z/=10;
			}
			if(!data[du])
			{
				dp[i]=1;
			}
		}
	}
}
void sum_prime()
{
	int sum=0,dum,m=0,z;
	for(i=0;i<=SIZE;i++)
	{
		if(dp[i])
		{
			sum+=1;
		}
		nop[i]=sum;
	}
}
int main()
{
	long test;
	sieve();
	is_dp();
	sum_prime();
	cin >> test;
	for(long i=0;i<test;i++) 
	{
		cin>>a>>b;
		cout<<nop[b]-nop[a-1]<<endl;
	}
	return 0;
}

Code: Select all

	int ds[SIZE];
	int dsum(int n){
		int &ret = ds[n];
		if(-1!=ret)return ret;

		if(n<10)return ret=n;

		return ret = n%10 + dsum(n/10);
	}

	void is_dp(){
		long x,z,ct=0,du,m=0;
       memset(ds,-1,sizeof(ds));

		for(i=0;i<SIZE;i++)
       {
          if(!data[i])
          {
             du = dsum(i);
			 if(!data[du])
             {
                dp[i]=1;
             }
          }
       }	
	}

Code: Select all

Removed after AC

Code: Select all

#include<iostream>
#include<cmath>
using namespace std;
bool prime[1000001];
bool dprime[1000001];
void seive()
{
     int m=1000;
     memset(prime,true,sizeof(prime));
     prime[0]=false;
     prime[1]=false;
     for(int i=2;i<=m;i++)
     if(prime[i]) 
     for(int k=i*i;k<=1000000;k+=i)
                  prime[k]=false;
                  
     memset(dprime,false,sizeof(dprime));
     dprime[0]=false;
     dprime[1]=false;
     for(int j=2;j<=1000000;j++)
     {
             int sum=0,num=j;
             while(num>=1)
             {
                          sum+=num%10;
                          num=num/10;
             }
             if(prime[sum])
             dprime[j]=true;
     }        
}
int main()
{
    int test,a,b;
    seive();
    scanf("%d",&test);
    while(test--)
    {
              scanf("%d %d",&a,&b);
              int n,count=0;
              for(n=a;n<=b;n++)
              {
                               if(prime[n] && dprime[n])
                               count++;                              
              }
              printf("%d\n",count);
    }
    system("pause");
}

Code: Select all

removed