TopCoder problem "PrimeStatistics" used in SRM 261 (Division I Level One , Division II Level Two)



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

0)
    
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.
1)
    
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.
2)
    
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.
3)
    
1
200000
2
Returns: 1
Almost all primes are odd; the only even prime is 2.
4)
    
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.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4661

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7995&pm=4661

Writer:

misof

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Simple Math, Simple Search, Iteration