Generate a random number that meets a given predicate

I would like to be able to generate random numbers that all meet a given predicate, for example only generate random numbers that are even or prime. Is there an algorithm to do this in a relatively efficient way? The way I have found to do this is to go brute-force:

let randIntSatisfy (randGenerator: System.Random) (satisfy: int -> bool) =
    // The maximum number of tries before returning `None`
    let maxTry = 100

    let rec inner i =
        function
        | num when satisfy num -> Some num
        | num when not (satisfy num) && (i < maxTry) -> inner (i + 1) (randGenerator.Next())
        | _ -> None

    inner 0 (randGenerator.Next())

let example =
    let randGen = new System.Random()

    seq { for _ = 0 to 10 do
              yield randIntSatisfy randGen (fun x -> x % 2 = 0) }

This code will not loop forever but will not guarantee to find a number that satisfies the given predicate (assuming such a number exists of course, if I ask for a negative number, then the function will return None all the time for example). Is there a way to do a little better than that?

PS: I've used F# here, but I'm not specifically asking for a language-specific answer.