10533 - Digit Primes

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

10533 - Digit Primes

Post by Dominik Michniewski » Tue Jul 29, 2003 2:23 pm

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Tue Jul 29, 2003 3:11 pm

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
Kalo mau kaya, buat apa sekolah?

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Jul 29, 2003 3:54 pm

could you tell me a way to avoid tle for this problem???
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Jul 29, 2003 4:08 pm

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

newtype feng
New poster
Posts: 8
Joined: Thu Jul 31, 2003 2:36 pm

Post by newtype feng » Thu Jul 31, 2003 3:12 pm

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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Jul 31, 2003 3:31 pm

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie » Sat Aug 02, 2003 5:30 pm

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.
Retired from SJTU Accelerator 2004

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur » Sun Aug 17, 2003 11:55 am

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

ericschmidt
New poster
Posts: 16
Joined: Mon Jan 06, 2003 9:27 pm
Location: Grosskrut, Austria

Post by ericschmidt » Tue Aug 19, 2003 5:50 am

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
New poster
Posts: 16
Joined: Mon Jan 06, 2003 9:27 pm
Location: Grosskrut, Austria

Post by ericschmidt » Wed Aug 20, 2003 5:18 am

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
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur » Fri Aug 22, 2003 1:45 pm

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

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Location: SUST,BANGLADESH
Contact:

Post by razibcse » Mon Oct 13, 2003 9:16 pm

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
Last edited by razibcse on Mon Oct 20, 2003 2:52 pm, edited 1 time in total.
Wisdom is know what to do next; virtue is doing it.

ericschmidt
New poster
Posts: 16
Joined: Mon Jan 06, 2003 9:27 pm
Location: Grosskrut, Austria

Post by ericschmidt » Tue Oct 14, 2003 6:28 am

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
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Oct 14, 2003 8:08 am

Finally I got Acc :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Post by supermin » Mon Nov 03, 2003 7:44 am

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;
}

Post Reply

Return to “Volume 105 (10500-10599)”