In this Kata, you will be given a number and your task will be to return the nearest prime number. 

```Haskell
solve(4) = 3. The nearest primes are 3 and 5. If difference is equal, pick the lower one. 
solve(125) = 127
```

We'll be testing for numbers up to `1E10`. `500` tests.

More examples in test cases. 

Good luck!

If you like Prime Katas, you will enjoy this Kata: [Simple Prime Streaming](https://www.codewars.com/kata/5a908da30025e995880000e3)

Difficulty: introductory

Starter code:

def solve(n):
	

Solutions:
def solve(n):
    print('starting with {0}'.format(n), flush=True)

    def is_prime(p):
        if p % 2 == 0 :
            return False
        for x in range(3,int(p**.5)):
            if p % x == 0:
                return False
        return True
        #return not any([p%x==0 for x in range(3,int(p**.5))])

    if is_prime(n):
        return n
    step = (n%2) + 1
    while 1:
        if is_prime(n-step):
            return n-step
        elif is_prime(n+step):
            return n+step
        else:
            step += 2
    return None



def isPrime(n): 
    if n < 2:
        return False 
    for i in range(2,int(n**.5)+1): 
        if not n%i:
            return False
    return True 


def solve(n): 
    if isPrime(n):
        return n
    add = 1
    rem = 1 

    ans = None 
    while True: 
        if isPrime(n+add):
            ans = n+add 
        if isPrime(n-rem):
            ans = n-rem
        if ans != None:
            return ans 
        add += 1
        rem += 1

is_prime = lambda n: n in (2, 3) or n > 3 and n % 2 and n % 3 and all(n % f and n % (f + 2) for f in range(5, int(n ** .5) + 1, 6))
solve = lambda n: next(p for gap in __import__('itertools').count(0) for p in (n - gap, n + gap) if is_prime(p))

def solve(n):
    i = 2
    if n%2==0:
        i = 1
    if IsPrime(n):
        return n
    while True:
        temp = n-i
        if IsPrime(temp):
            return temp
        temp = n+i
        if IsPrime(temp):
            return temp
        i+=2

def IsPrime(n):
    if n %2 ==0:
        return False
    for i in range(3,int(n**0.5),2):
        if n % i == 0:
            return False
    return True

from math import sqrt
def solve(n):
    
    ls = []
    
    for i in range(n, n+300):
        
        temp = True
        for j in range(2, int(sqrt(n)) + 10):
            
            if i % j == 0 and i != j:
                temp = False
                break
        if temp: 
            ls.append(i)
            break
    
    
    for i in range(n - abs(n-ls[0]), n+1):
        
        temp = True
        for j in range(2, int(sqrt(n)) + 10):
            
            if i % j == 0 and i != j:
                temp = False
                break
        if temp: 
            ls.append(i)
            
    if len(ls) > 1:
        return ls[-1]
    return ls[0]

from itertools import chain, count


def is_prime(n):
    return n == 2 or (n > 2 and n % 2 and all(n % i for i in range(3, int(n**0.5)+1, 2)))


def solve(n):
    deltas = chain([0], chain.from_iterable([-i, +i] for i in count(1)))
    return next(n+delta for delta in deltas if is_prime(n+delta))

from itertools import count
from bisect import bisect_left as bisect

n = 100005                                    # Sieve up to (10**10)**.5 + 5
sieve, primes = [0]*((n>>1)+1), [2]           # optimized sieve (store only odd numbers
for i in range(3, n+1, 2):
    if not sieve[i>>1]:
        primes.append(i)
        for j in range(i**2>>1, (n+1)>>1, i): sieve[j] = 1
    
def solve(n):
    if n%2 and n>>1 < len(sieve) and not sieve[n>>1]: return n                    # easy check: prime if sieve element is set to False
    
    idx = bisect(primes,n)                                                        # Insertion point of n in the prime list
    return bigSearch(n, idx) if idx == len(primes) \
           else min( primes[max(0,idx-1):idx+2], key=lambda x: (abs(x-n), x))     # fast look up in the list of primes (check element before, under and after the insertion point)

def isPrime(n, iSq): return all(n%x for x in primes[:iSq])

def bigSearch(n, idx):
    iSq = bisect(primes,n**.5,0,idx)                                              # insertion point of n**.5 in the prime list (for complex primality check)
    isPair = not n%2
    for x in count(0):
        for c in [-1,1]:
            p = n+c*(2*x + isPair)
            if isPrime(p, iSq): return p