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

Post by lighted » Wed Nov 19, 2014 11:24 am

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[1000001] 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

Post by bgcsaif » Thu Mar 26, 2015 8:59 am

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

Post by bgcsaif » Sun May 03, 2015 12:43 pm

Is there anyone? I need help....

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

Re: 10533 - Digit Primes

Post by oja » Thu May 14, 2015 2:07 am

Make an array(let's say "arr") that stores the number of digit primes up to the value of the index. For example, arr[10] 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[0] is 0. Next is 1. It isn't either so arr[1] = arr[0] + 0 = 0 + 0 = 0.
Next is 2. It is, so arr[2] = arr[1] + 1 = 0 + 1 = 1. Then 3. It is digit prime. So arr[3] = arr[2] + 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.

Post Reply

Return to “Volume 105 (10500-10599)”