Page **4** of **8**

### now RTE, 10533

Posted: **Wed Jun 28, 2006 7:00 pm**

by **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:

thanx for reading.

Posted: **Wed Jun 28, 2006 8:16 pm**

by **mamun**

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

Posted: **Thu Jun 29, 2006 12:33 pm**

by **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...

Posted: **Thu Jun 29, 2006 9:04 pm**

by **deena sultana**

Sohel n Mamun,

thank u soooooooooooo much.

At last i get AC.

.

So kind of u both.

Thanks again.

Posted: **Tue Jul 04, 2006 2:39 pm**

by **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 ?

### 10533 digit primes WA

Posted: **Thu Jul 06, 2006 2:55 pm**

by **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.

### Re: 10533 digit primes WA

Posted: **Sun Jul 23, 2006 11:32 pm**

by **Martin Macko**

ayeshapakhi wrote: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
```

### Re: 10533 digit primes WA

Posted: **Sun Jul 23, 2006 11:38 pm**

by **Martin Macko**

### thanks to martin

Posted: **Wed Aug 02, 2006 6:58 am**

by **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..

Posted: **Sat Mar 31, 2007 3:22 pm**

by **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!

### TO NEWTON...

Posted: **Sat Mar 31, 2007 5:14 pm**

by **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

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

### I have got ACC in 1.7 sec, Is there any better method?

Posted: **Tue May 15, 2007 8:51 am**

by **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.

Posted: **Tue May 15, 2007 9:04 am**

by **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.

### 10533(Runtime error)

Posted: **Tue Jul 24, 2007 1:32 pm**

by **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;
}
```

Posted: **Tue Jul 24, 2007 3:53 pm**

by **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;
}
}
```