-2
Find the digit which occurs the most in a range of prime numbers.
Input:
Two numbers, p
and q
, specifying the range; the range includes both p
and q
.
Output:
The digit that occurs most frequently in that range of prime numbers. If two or more digits are tied, all of them should be outputted.
Winning Criteria:
Fastest code to complete (insert 1+ specific test cases here) wins.
Example
Input: 21 40
Output: 3
Explanation
The prime numbers in the range 21 40
are 23
, 29
, 31
, and 37
. Within these numbers, 2
occurs 2 times, 3
occurs 3 times, and 1
, 7
and 9
occur 1 time each. Thus, as 3
appears the most, the correct output is 3
.
I've added the tag corresponding to your chosen winning criterion. Please have a look at the tag wiki and consider clarifying especially the second and third question there.
– Martin Ender – 2015-09-11T11:18:49.347"Two numbers p and q specifying the range" how? Inclusive, exclusive, one of each? What should the output be if there's a tie? What should it be if the tie is because there are no primes in the range? And are you really sure you want to do a [tag:fastest-algorithm] which involves primality testing, bearing in mind that the running time of the best known algorithm depends on the correctness or otherwise of a long-open problem (the generalised Riemann hypothesis)? – Peter Taylor – 2015-09-11T11:54:19.337
3I think this could be an OK question if the winning criterion is least number of bytes, and all of Peter's questions are answered. – Stewie Griffin – 2015-09-11T12:21:44.990
@PeterTaylor First of all Primality testing has a poly time algorithm (Agarwal,2002) . Second by fast algorithm I never said it has to be poly time, I just wanted an algorithm better than just bruteforce. Third I have specified range as inclusive. – alienCoder – 2015-09-11T13:10:01.840
I know that PRIMES is in P: the developments of AKS techniques are precisely what's behind my comment about the GRH. The best AKS variant is in Õ(n^6) if the GRH is false, and Õ(n^4) if the GRH is true. Moreover, the previous [tag:fastest-algorithm] question about primes has a few answers, not a single one of which has a stated score. I don't think [tag:fastest-algorithm] and primes are a good fit for each other. – Peter Taylor – 2015-09-11T14:16:06.920
1@alienCoder Could you define more precisely what should happen in the case of finding two (or more) digits which occur the most, like if there are
4
threes and fives? Also, what do you mean by input and output? Function parameters and return value? STDIN and STDOUT? – Toothbrush – 2015-09-11T18:19:03.537239 is divisible by 3. It's not prime. – Zach Gates – 2015-09-11T22:47:29.703
@alienCoder What do you mean as least time complexity? Big O notation ? Note that two algorithms with the same time complexity given in terms of big O notation may differ in the time of execution by an arbitrarily big constant factor. Maybe consider [tag:fastest-code] instead? This could make this question more "popular". – pawel.boczarski – 2015-09-12T14:17:55.287