PrimeStatistics
SRM 261 · 2005-08-30 · by misof
Problem Statement
It is a known fact that prime numbers are not evenly distributed. For example, almost all primes give the remainder 1 or 5 when divided by 6 (the only two exceptions are the primes 2 and 3). Your task is to write a program that will help explore this phenomenon.
You will be given three integers: lowerBound, upperBound and modulo. Return the remainder that occurs most often when we take all primes in the set { lowerBound, lowerBound+1, ... upperBound } and divide each of them by modulo. If there are multiple remainders that occur most often, return the smallest of them.
Notes
- A prime number is a positive integer that has exactly two divisors. The first few primes are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
Constraints
- lowerBound and upperBound are between 1 and 200,000 inclusive.
- lowerBound is less than or equal to upperBound.
- modulo is between 2 and 1000 inclusive.
3 14 5 Returns: 3
The primes in this interval are: 3, 5, 7, 11 and 13. Their remainders when divided by 5 are 3, 0, 2, 1 and 3, respectively. Thus the most common remainder is 3.
3 33 1000 Returns: 3
In this case each of the primes gives a different remainder. According to the tie-breaking rule the smallest of them is returned.
25 27 17 Returns: 0
There are no primes in this interval. Each remainder occurs zero times, thus each of them is the most common remainder. Zero is the smallest possible remainder. Thus, according to the tie-breaking rule, zero is returned.
1 200000 2 Returns: 1
Almost all primes are odd; the only even prime is 2.
1 1000 6 Returns: 5
As mentioned in the introduction, almost all primes give the remainder 1 or 5 modulo 6. In this interval there are more primes of the second kind.
Submissions are judged against all 154 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PrimeStatistics with a public method int mostCommonRemainder(int lowerBound, int upperBound, int modulo) · 154 test cases · 2 s / 256 MB per case