Marathon Match 58 - Marathon Match 58

Key Information

The challenge is finished.
Show Deadlines

Challenge Overview

Problem Statement

    A prime number is a number that is divisible by only itself and one. In this problem we will say that a prime number p is x-isolated at distance (a,b) if there there are at most x primes (including p) between (p-a) and (p+b), inclusive. You are given the numbers a, b and x. Your task is to find the smallest prime p between a+2 and 263-1-b, inclusive, such that p is x-isolated at distance (a,b), and return a String which contains its decimal notation. For example, for x=2 and a=b=5, the smallest possible value is 23, as the only primes in [18,28] are 19 and 23.

Your score for each individual test case will simply be the value you return (or 0 if your value does not meet the criteria above). Invalid returns (a string which is not a prime number, a number outside of the bounds or a number which is not sufficiently isolated) result in a score of 0 and don't contribute to the overall score. Assuming your return is valid for a test case, it's contribution to your overall score will be BEST/YOU, where BEST is the best (lowest) value found for this test case by any competitors and YOU is your value. The total score will simply be the sum of these ratios over all test cases.


Parameters:int, int, int
Method signature:String findPrime(int x, int a, int b)
(be sure your method is public)


-java.math.BigInteger.isProbablePrime(200) is used for primality testing.
-If a test case has no valid returns, everyone will receive a 0 for that test.


-x is chosen uniformly at random in [1,500]
-a and b are chosen uniformly at random in [4x,25x]
-The size of your code is limited to 100K (102400 bytes)
-The time limit is 20 seconds. The memory limit is 1024M.


Returns: "x = 2
a = 5
b = 5
Returns: "x = 410
a = 5954
b = 1916
Returns: "x = 400
a = 4067
b = 9810
Returns: "x = 87
a = 922
b = 630
Returns: "x = 76
a = 1127
b = 546
Returns: "x = 312
a = 7649
b = 4383
Returns: "x = 449
a = 3232
b = 8777
Returns: "x = 489
a = 11822
b = 8438
Returns: "x = 126
a = 2399
b = 1183
Returns: "x = 500
a = 12500
b = 12500

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.


Topcoder will compensate members in accordance with our standard payment policies, unless otherwise specified in this challenge. For information on payment policies, setting up your profile to receive payments, and general payment questions, please refer to ‌Payment Policies and Instructions.