10533 - Digit Primes

[Dominik Michniewski]

Could anyone tell me what is the answer for this input?

1 1000000

I've got 30123 but I've got WA ....

Best regards
DM

[titid_gede]

i think there is no input like that, maximum is 999999

try this input :

Code: Select all

5
1 999999
11 11
10 10
11 20
11 29

output should be : (according to my ACC prog)

Code: Select all

30123
1
0
1
3 

hope this helps.

regards,

titid

[anupam]

could you tell me a way to avoid tle for this problem???

[Dominik Michniewski]

titid, I got the same results .... as you ...
hmmm I don't know what can I do wrong ...
Could I send you my code ?

anapum: use DP

Best regards
DM

[newtype feng]

the first number and the second number can be change
like this:
999999 1

[Dominik Michniewski]

I don't think so ... I don't consider such case and in problem description is sentence which clearly tell us, that first number is not greater than second ....

Best regards
DM

[hujialie]

To Dominik:

My ACed programme also doesn't consider the case that t2<t1;
try these two test cases:

Input:
39025 489248
3387 67184

Output:
14155
2610

One thing more,did you use long type for N?N can also be as large as 500000.

Hope this can help.

[Faizur]

i m also getting tle with this problem .Can any one tell me briefly an efficient way to solve the problem.

[ericschmidt]

Dear Faizur,

A few hints for an efficient solution of Shahriar’s problem „Digit Primes“ (10533). I’ve just started working on the program ... these are the major parts of my „design“:

1.)
To count the number of „Digit Primes“ within the range [t1, t2] means to first check if the number is prime and then to check the digit sum being prime (which is the „weaker sieve“). For both activities You need a look up table of the prime numbers up to t2 which can be produced by using the „sieve of Eratosthenes“. Note that you only have to strike out the multiples of the primes up to sqrt(t2) to get the complete look up table of all prime numbers up to t2. I think performing this once for a t2_max=999999 should be fine for this problem.

2.)
You should also use an efficient algorithm to calculate the digit sum – try this one:

[c]int digit_sum(int number)

{ int sum = 0;
do
{
sum += number;
number /= 10;
sum -= number*10;
} while (number);
return sum;
}[/c]
3.)
Perhaps some of the input case ranges overlap and performing some bookkeeping for reusing ranges which have already been checked might pay off.

Yours, Eric

[ericschmidt]

Sorry folks,

I have to revise my own posting after a few learning cycles with TLE. I finally got AC (1.664 seconds). Here some new (and better) hints:

A.) Forget the algorithm for calculating the digit sum! When going up through the odd numbers (3,5,7, ...) and checking for digit primes you can keep track of the digit sum in parallel.

B.) The look up table containing TRUE for digit primes and FALSE for the rest has to be "integrated" (once) to prevent having to loop from t1 to t2 for each input case. This can be done in parallel with the loop in (A) and then the number of digit primes is generally the expression:

(integrated_list[t2] - integrated_list[t1-1])

... where integrated_list[] is an array starting with the counter value 0 and incrementing at each index of a digit prime.

Yours, Eric

[Faizur]

Thank u Eric for ur help.I need to rethink about the problem

[razibcse]

Can you guys tell me, why on earth this program gets RTE(Floating point Exception)...I am totally depressed seeing this message again & again...

please someone help me out...

At last I got AC...I had to change my prime generating function...

thanks guys

Code: Select all

Deleted

Razib

[ericschmidt]

Hi razibcse!

The only floating point operation I can see at a first glance is the sqrt() function. I assume you passed a "very large" (and therefore overflowed to negative) 'long' argument to sqrt(). Watch out for the range you are using.

Yours, Eric

[Dominik Michniewski]

Finally I got Acc

Best regards
DM

[supermin]

Cound anyone help with my code? ><"
I try many cases, but still can't find the problem.

Code: Select all

#include<stdio.h>

typedef struct {
	int digitprimestate;
	long key;
}NUM;

NUM array[1000002];

int primestate[1000002];
long getdigitnum(long n);

int main()
{
	long digitprimecount = 2;
    long cases;
    long left,right;
    long i,j;
    
	primestate[1] = 0;
	array[1].digitprimestate = 0;
	array[1].key = 0;

	primestate[2] = 1;
	array[2].digitprimestate = 1;
	array[2].key = 1;

	primestate[3] = 1;
	array[3].digitprimestate = 1;
	array[3].key = 2;

	primestate[4] = 0;
	array[4].digitprimestate = 0;
	array[4].key = 2;

    for(i=5;i<1000000;i+=2){
        for(j=3;j*j<=i;j+=2)
            if(i%j==0) break;
		if(i%j!=0){
            primestate[i]=1;
			if( primestate[ getdigitnum(i) ] == 1 ){
				array[i].digitprimestate = 1;
				array[i].key = ++digitprimecount;
			}
		}
		else{
			array[i].digitprimestate = 0;
			array[i].key = digitprimecount;			
		}
		array[i+1].digitprimestate = 0;
		array[i+1].key = digitprimecount;
    }

    scanf("%ld",&cases);
    while(cases-->0){        
        scanf("%ld %ld",&left,&right);
        printf("%ld\n",array[right].key - array[left-1].key);
    }
    
    return 0;
}

long getdigitnum(long n){
    long a=0;
    for(;n;n/=10)
        a+=n%10;
    return a;
}