Find the digit occurring the most in a range of prime numbers

-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.

alienCoder

Posted 2015-09-11T09:59:52.507

Reputation: 97

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.537

239 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

Answers

1

Python 3

import collections
p=lambda n:n>1 and all(n%i for i in range(int(n**0.5),1,-1))
print(collections.Counter(''.join(map(str,filter(p,range(*map(int,raw_input().split(' '))))))).most_common(1)[0][0])

Probably not the best way it can be done, but a start. (196 bytes)

Time Specs

Using Python's builtin code timer module, timeit, I got these times for each listed range.

(1,       11):      0.000084381103520
(1,      101):      0.000338881015778
(1,     1001):      0.003911740779880
(1,    10001):      0.071979818344100
(1,   100001):      1.785329985620000
(1,  1000001):     54.977741956700000
(1, 10000001):   1700.231099130000000

It can go over a range of a million numbers in under a minute.

Usage

$ python test.py
21 41
3
$ python test.py
51 89
7
$ python test.py
201 501
3

Ungolfed

import collections

def is_it_prime(n):
    if n > 1:
        if all(n % i for i in range(int(n ** 0.5), 1, -1)):
            return True
    return False

start, stop = raw_input.split(' ', 1)

primes = ""
for p in range(int(start), int(stop)):
    if is_it_prime(p):
        primes += str(p)

counter = collections.Counter(primes).most_common(1)
print(counter[0][0])

Zach Gates

Posted 2015-09-11T09:59:52.507

Reputation: 6 152

Just so you know, winning criteria is time complexity, not byte count :) – Kade – 2015-09-12T00:02:04.217

I saw; that's why I added the "Time Specs" section. :P @Shebang – Zach Gates – 2015-09-12T00:02:45.467

Just making sure you know if you want to update you could un-golf to make updating much easier. Nice work though! :) – Kade – 2015-09-12T00:04:35.837

Added an ungolfed version. @Shebang – Zach Gates – 2015-09-12T04:07:01.517