10533 - Digit Primes

[deena sultana]

i m very much annoyed with this 10533, 1st it get tle & tle, and now its getting RTE.
now it seems very hard for me to think more about this problem.
Anyone help me, plz?plzzzzzzzzzzz.

here is my code:

Code: Select all

removed after AC.

thanx for reading.

[mamun]

You're declaring large arrays in the main() function. Declare them static or global. Moreover, you might get memory limit exceeded.

[sohel]

The cause of RTE is because of the declaration of huge Array inside the main function..
.. making it global will solve the problem. [ like mamun said ]

But it will not get MLE since two integer array of size 10^6 and 1 boolean array of size 10^6 doesn't exceed the given memory limit..

Your code is correct, I made the necessary changes and it did get AC.

And remove your code after submitting...

[deena sultana]

Sohel n Mamun,

thank u soooooooooooo much.

At last i get AC. .

So kind of u both.

Thanks again.

[Kallol]

Well,
I also got ACC in that problem but thats not what i am bothered about but its the timing . It took me 2.090 CPU and what I found in the list that people solved it much more efficiently .

My algo is as same as it was told here. Can anyone tell me whether there is a better algorithm to solve this problem more efficiently ?

[ayeshapakhi]

i wonder wheres the mistake!
pls help!!!
thanks for any help;;;

Code: Select all

#include <stdio.h>  // 10533 submit
#include <math.h>

#define L 1
#define U 1000005
#define D 1000005

bool all[D];
bool digit[D];
inline void seive(void);
long count[D];

   *********removed after AC
/*
12 
1 999999 
1 1 
1 10 
9 12 
240320 240350 
3 20 
204525 505639 
200 300 
1000 3000 
2056 31256 
999984 999999 
999985 999985 


OUTPUT: 

30123 
0 
4 
1 
0 
4 
9096 
8 
133 
1364 
0 
0
*/

pls supply me some critical I/O
thanks again.

[Martin Macko]

i wonder wheres the mistake!
pls help!!!
thanks for any help;;;

Your solution's not working for:

Code: Select all

10
291188 931733
638630 694459
238760 749751
762142 886106
517246 642611
203388 491378
369474 521162
515894 899808
181906 384967
89477 457040

My AC's output is

Code: Select all

18179
1558
14793
3382
3592
8699
4463
10686
6237
11553

[Martin Macko]

And btw, there is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question instead of creating a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=11056, http://online-judge.uva.es/board/viewtopic.php?t=7453, http://online-judge.uva.es/board/viewtopic.php?t=3600 and http://online-judge.uva.es/board/viewtopic.php?t=4503)

[ayeshapakhi]

dear martin,
thanks a tonnn for ur help.
ur i/o helped me much.
what a stupid i am. i flagged an array but using another in my code.....
foolish!!!!
thanks a lot..

[newton]

i used normal sieve mathod to count. that is the number and digit prime or not.
but OJ says memory limit exceded. now how can i minimize the memory limit?

if i changed the prime[10000001] to prime[1000001] it gets CE!
but why?

Code: Select all

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

void set_prime(void);
long sod(long);

long prime[10000001];

int main()
{
	long tc,t1,t2,j,count;

	set_prime();
	scanf("%ld",&tc);
	while(tc--)
	{
		scanf("%ld %ld", &t1,&t2);
		count = 0;
		for(j = t1; j <= t2; j++)
		{
			if(prime[j])
			{
				if(prime[sod(j)])
					count++;
			}

		}
		printf("%d\n", count);
	}
	return 0;
}

void set_prime()
{
	long i,j,index;
	for(i=1;i<=1000000;i++)
		prime[i]=1;

	prime[1] = 0;
	for(i=2;i<=sqrt(1000000);i++)
		if(prime[i]==1)
			for(j=2;i*j<=1000000;j++)
				prime[i*j]=0;
}


long sod(long num)
{
	long sum = 0;
	while(num)
	{
		sum += num % 10;
		num = num / 10;
	}
	return sum;
}

advanced thanx!

[nymo]

to Newton, your algo is slow... even if you don't get CE, it will probably be a TLE...

in your code, you use

Code: Select all

long prime[10000001]; 

just for marking whether i is prime or not; 1 and 0 respectively.
you can obviously use

Code: Select all

#define SIZE THE_SIZE_YOU_WANT
char prime[SIZE];

it will reduce the size to 1/4 char is 1 byte and it can be used to hold integers in that range.

you can use this SIEVE code

Code: Select all

#define SIZE THE_SIZE_YOU_WANT

char composite[SIZE];

void sieve(void)
{
	int i, j, k;

	composite[0] = 1;
	composite[1] = 1;

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

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

	
	}
}

you can use the fact that global arrays are initialized with 0

[tanaeem]

I have detected prime by ruunig seive.
Then created a dprime array, if ith element id a digit prime then put there 1. I have done this using the seive, if both i and digitsum(i) is prime then dprime=1;

then created another array containing cumilitive sum of the dprimr array.
Then printed output as input given in constant time.
But it took 1.7 sec time. is there any better method?
I see someone have got AC in 0.250 time.

[sohel]

There are optimized versions of finding primes using sieve.
Since you are printing the output in constant time, I guess your 'sieve method' isn't fast enough.

[ishtiaq ahmed]

Hi, i cannot understand why i am facing runtime error. I have checked array size again and again. Please try to help me. Here is my code

Code: Select all

#include<stdio.h>

#define SIZE 1000001

long  a,b,data[SIZE]={0},cas,i,j;
void s (void);
long sum_prime(void);


int main()
{
	long k,result,cas;
	s();
	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;
	data[0]=1;
	data[1]=1;
	for(i=4;i<SIZE;i+=2)
		data[i]=1;
	for(i=3;i<SIZE;i+=2)
		for(j=i;i*j<SIZE;j++)
			if(!data[i*j])
				data[i*j]=1;
}



long sum_prime(void)
{
	int sum=0,dum,m=0,z;
	for(i=a;i<=b;i++)
		if(!data[i])
		{
			z=i;dum=0;
			while(z)
			{
				m=z%10;
				dum +=m;
				z /=10;
			}
			if(!data[dum])
				sum++;
		}
	return sum;
}

[hamedv]

change your sieve function to

Code: Select all

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