Is it possible to train a machine learning model to predict the next prime number? As there are no patterns to prime numbers. Is there any way in which ML could predict it? 
 A: Search for mathematical formulae (in a restricted alphabet) which satisfies the data. Basically, the hypothesis space is the set of all valid formulae.
For example, $\min \{z \in \mathbb{N}\ |\ 
(z > x) \wedge (\not \exists y: (1 < y < z) \wedge (y | z)) \}$ predicts the next prime after $x$.
Given that I've used 9 unique symbols here -- and a total of 19 symbols, this seems not too intractable a search space -- and there may be an even more compact solution. 
The simplest algorithm would be a brute force search in ascending length, although you could get clever about it and try some sort of genetic algorithm. The search concludes when you find a formula which satisfies all of your test cases, at which point you should've learned a perfect predictor -- given that you use sufficiently many test cases, I doubt there is a shorter incorrect formula than the correct one.
A: With which accuracy ? And with which (algorithmic) complexity ?
One can extract "features" from an integer (with a constant time) :


*

*Does it end by 2 ?

*Does it end by 5 ?

*Does it end by ... ?

*Is the sum of its number a multiple of 3 ?

*Is the sum of its number a multiple of 11 ?


And train any model on these features (random forest...), the label being "is my number prime".
I guess with this you would be much better than a random classifier. 
Now you can add more complex features (but they may be longer to evaluate than simply check from being prime)


*

*Is it a square of an integer ?

*Is it a Mersenne number ?

*Does it have the form $3k+1$ ? (or any other form)

*...

