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.
Definition
- Class:
- PrimeStatistics
- Method:
- mostCommonRemainder
- Parameters:
- int, int, int
- Returns:
- int
- Method signature:
- int mostCommonRemainder(int lowerBound, int upperBound, int modulo)
- (be sure your method is public)
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.
Examples
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.
1
1
2
Returns: 0
2
2
2
Returns: 0
3
3
2
Returns: 1
4
4
2
Returns: 0
1
1
10
Returns: 0
2
2
10
Returns: 2
3
3
10
Returns: 3
4
4
10
Returns: 0
1
4
7
Returns: 2
49
49
2
Returns: 0
342
344
13
Returns: 0
117649
117650
4
Returns: 0
196248
196250
17
Returns: 0
2967
2991
6
Returns: 1
2963
2991
6
Returns: 5
1
200000
2
Returns: 1
1
200000
3
Returns: 2
1
200000
997
Returns: 305
1
200000
1000
Returns: 13
47
193252
843
Returns: 721
147
192252
743
Returns: 168
1
1
3
Returns: 0
1
200000
3
Returns: 2
1
2
3
Returns: 2
1
1
2
Returns: 0
1
2
7
Returns: 2
1
3
2
Returns: 0
1
1
10
Returns: 0
1
1
4
Returns: 0
1
1
5
Returns: 0
1
200000
2
Returns: 1
3
14
5
Returns: 3
1
2
4
Returns: 2
1
200000
798
Returns: 433
1
2
100
Returns: 2
200000
200000
1000
Returns: 0
2
2
3
Returns: 2
5
5
2
Returns: 1
195473
198059
506
Returns: 41
1
200000
5
Returns: 3
3
33
1000
Returns: 3
2
7
5
Returns: 2
199967
199999
3
Returns: 1
2
2
10
Returns: 2
2
2
4
Returns: 2
1
1000
1000
Returns: 2
17
17
3
Returns: 2
1
200000
1000
Returns: 13
1
14
5
Returns: 2
95
105
2
Returns: 1
1
7
3
Returns: 2
1
200000
19
Returns: 4
5
7
6
Returns: 1
1
1
7
Returns: 0
1
200000
999
Returns: 727
4
189087
875
Returns: 761
7
29
3
Returns: 2
2
3
2
Returns: 0
20001
100000
5
Returns: 2
2
5
6
Returns: 2
199931
199931
10
Returns: 1
13
13
20
Returns: 13
1
200000
6
Returns: 5
2
2
1000
Returns: 2
1
200000
7
Returns: 5
1
2
2
Returns: 0
2
1000
17
Returns: 11
14
15
100
Returns: 0
17
17
5
Returns: 2
3
17
5
Returns: 2
2
5
4
Returns: 1
1
200000
918
Returns: 193
121
121
2
Returns: 0
1
3
7
Returns: 2
2
4
2
Returns: 0
1
17
991
Returns: 2
196249
196249
2
Returns: 0
2
5
5
Returns: 0
5
14
3
Returns: 1
23
37
3
Returns: 1
9
200
10
Returns: 3
2
9
3
Returns: 2
1
200000
997
Returns: 305
5
7
7
Returns: 0
2
2
5
Returns: 2
1
1
3
Returns: 0
1
200000
3
Returns: 2
1
2
3
Returns: 2
1
1
2
Returns: 0
1
2
7
Returns: 2
1
3
2
Returns: 0
1
1
10
Returns: 0
1
1
4
Returns: 0
1
1
5
Returns: 0
1
200000
2
Returns: 1
3
14
5
Returns: 3
1
2
4
Returns: 2
1
200000
798
Returns: 433
1
2
100
Returns: 2
200000
200000
1000
Returns: 0
2
2
3
Returns: 2
5
5
2
Returns: 1
195473
198059
506
Returns: 41
1
200000
5
Returns: 3
3
33
1000
Returns: 3
2
7
5
Returns: 2
199967
199999
3
Returns: 1
2
2
10
Returns: 2
2
2
4
Returns: 2
1
1000
1000
Returns: 2
17
17
3
Returns: 2
1
200000
1000
Returns: 13
1
14
5
Returns: 2
95
105
2
Returns: 1
1
7
3
Returns: 2
1
200000
19
Returns: 4
5
7
6
Returns: 1
1
1
7
Returns: 0
1
200000
999
Returns: 727
4
189087
875
Returns: 761
7
29
3
Returns: 2
2
3
2
Returns: 0
20001
100000
5
Returns: 2
2
5
6
Returns: 2
199931
199931
10
Returns: 1
13
13
20
Returns: 13
1
200000
6
Returns: 5
2
2
1000
Returns: 2
1
200000
7
Returns: 5
1
2
2
Returns: 0
2
1000
17
Returns: 11
14
15
100
Returns: 0
17
17
5
Returns: 2
3
17
5
Returns: 2
2
5
4
Returns: 1
1
200000
918
Returns: 193
121
121
2
Returns: 0
1
3
7
Returns: 2
2
4
2
Returns: 0
1
17
991
Returns: 2
196249
196249
2
Returns: 0
2
5
5
Returns: 0
5
14
3
Returns: 1
23
37
3
Returns: 1
9
200
10
Returns: 3
2
9
3
Returns: 2
1
200000
997
Returns: 305
5
7
7
Returns: 0
2
2
5
Returns: 2