I think Felipe Voloch has the right sense about the problem: you should expect to encounter a prime or a number which is a small number times a prime. Since you suggested probabilistic and did not mention that you wanted ONLY the desired number output, here is a start on your desired program.

Pick a desired small bound B, which will be the largest of the primes to be sieved out. Make B compatible with the desired running time of your eventual program, but I like Felipe's suggestion of $O(\text{log}^2N)$. Now for each prime $p$ up to B, compute the remainder of $N$ after dividing by the largest power of $p$ that is smaller than $N$. Use this to populate an array of length of your interval with powers of $p$ which are the factors of the corresponding numbers. This should take (B/log(B)) times $O(\text{log}N)$ time and space.

At this point you have several options. The simplest one is to perform the divisions and list out the cofactors as well as the small factors. Even with B smaller than Felipe's suggestion, you will most likely have printed out the complete factorization of one of the numbers. Use whatever time you have remaining to find it, either by doing quick primality tests on all the candidates or slow primality test on some appropriate subset. An alternative is to continue eliminating small factors, for once $p$ is larger than your $O(\text{log}N)$, you won't need to worry about picking powers, but can switch to doing gcd with 0 or 1 numbers in the interval.

In short, there is a way to make an efficient version which is morally equivalent to trial division, and still have time left over to pick with high chance of success the completely factored number.

**EDIT 2011.08.10** I got curious, so I asked a
question and did some computations with B=2, with the expectation that I would find very few intervals of the form $[N - \text{log}_2N ,N]$ which did not contain a prime or a power of 2 times a prime, or a power of 2. The data so far are contrary to my expectations: if I haven't messed up the programming, there are more than 200 such $N$ less than $10^5$. Although I still think the small intervals will contain a B-smooth number for B not too large, this recent data puts a measure of doubt in my mind.
**END EDIT 2011.08.10 **

Gerhard "Ask Me About System Design" Paseman, 2011.08.04