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

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10533 - Digit Primes

You could read this thread before posting.

Make precomputation in range 1..1000000 of all primes and sum of their digits using sieve of eratosthenes. Save in boolean array which of them is digit prime or not. Then precompute in array sum number of digit primes, such that sum = number of digit primes between 1 and i. Then process input. Using this array you can get answer in O(1). For each input t1 and t2 answer is sum[t2] - sum[t1 - 1]. By the way, sum of digits of a number can be also calculated using sprintf without making division and mod operations.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10533 - Digit Primes

I am tired of TLE for this problem.... First I tried it manual then I tried it with sieve method..... But yet I am having TLE.... Help me to with any clues plz.....
http://ideone.com/uTTQz8

bgcsaif
New poster
Posts: 38
Joined: Mon Sep 29, 2014 4:03 pm

Re: 10533 - Digit Primes

Is there anyone? I need help....

oja
New poster
Posts: 11
Joined: Fri Apr 24, 2015 5:34 pm

Re: 10533 - Digit Primes

Make an array(let's say "arr") that stores the number of digit primes up to the value of the index. For example, arr contains the number of digit primes
from 0 to 10. Fill this array before processing any input. Check if 0 is digit prime. It isn't. So arr is 0. Next is 1. It isn't either so arr = arr + 0 = 0 + 0 = 0.
Next is 2. It is, so arr = arr + 1 = 0 + 1 = 1. Then 3. It is digit prime. So arr = arr + 1 = 1 + 1 = 2. Do this up to the maximum upper limit. Use sieve of
eratosthenes to check for primality.

Now given an interval a and b, how many digit primes are there?It's just arr - arr[a - 1]. This is much faster and more efficient than counting the number of digit
primes from a to b for every query.