PROBLEM LINK-: CLICK HERE
PROBLEM SETTERS-: @aliencoder_07 @dcpandey
EDITORIALIST-: @dcpandey
DIFFICULTY-: Easy
PREREQUISITES-: Math,Number Theory
PROBLEM-: Alien is a coder at UIET CODING CLUB and he got a new problem on prime numbers. The problem states that given an integer N find the prime number which at minimum distance to N . If multiple answer is possible then output the smallest one of them . There are T number of test cases.
EXPLANATION-: Every Number can be represented in the form of (6k+i) where i is in between 0 to 5.So any number can be represented in atleast one of the forms 6k , 6k+1 , 6k+2 , 6k+3 ,6k+4 , 6k+5. Out of these numbers 6k +2 , 6k+4 are divisible by 2 and 6k +3 , 6k are divisible by 3. So the remaining are 6k+1 and 6k+5. 6k+5 can also be represented by 6k-1. So we can check first that the number is visible by 2 or 3,if so then return false.else check further starting from i=5(for, k==1, 6k-1=5) and till sqrt(n) that n%i is zero or n%(i+2) is zero or not.if yes at some time then return false.else increment i by 6.time complexity for checking a number prime or not is O(√(n/6))
SOLUTION-: CLICK HERE