-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
4threes 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