How to determine in polynomial time if a number is a product of two consecutive primes? How to determine in polynomial time if a number is a product of two consecutive primes?
All I can figure out is that if Cramér's conjecture is true, then we can use the AKS primality test to find $p_i < \sqrt n < p_{i+1}$, then check if $p_i * p_{i+1} = n$.  Is there some way to determine if a number is of this form in polynomial time that doesn't rely on any unproven assumptions?
Also, given that a number is of this form, what is the quickest way to factor it?  How fast will modern general-purpose factoring algorithms such as the quadratic sieve factor a product of consecutive primes?
 A: Let $x =\lceil \sqrt{n} \rceil$. Check if $x^2 - n$ is a square. If $x^2 - n = y^2$, check if $x+y$ and $x-y$ are primes, using a suitable primality test. If they are, check if there are any primes between $x-y$ and $x+y$. 
This also depends on Cramer's conjecture, of course.
Edit (7/24): Let $n = pq = (x+k)(x-k)$ where $p,> q$. Fermat's method is to compute $\sqrt{n+k^2}$ for many $k$ until one finds an integer. Then set $x = \sqrt{n+k^2}$ and $p = x+k, \, q = x-k$. 
To see how this can be sped up, use the Taylor approximation
$$
\sqrt{n+k^2} = \sqrt{n} \sqrt{1 + \frac{k^2}{n}} \approx \sqrt{n} \left( 1+ \frac{k^2}{2n}\right) = \sqrt{n} + \frac{k^2}{2\sqrt{n}}
$$
to see that if $\frac{k^4}{n}$ is small, then $0 < \sqrt{n+k^2} - \sqrt{n} < 1$ or so and simply rounding up from $\sqrt{n}$ will produce $k$ immediately, in one  step. That's the origin of the condition $k \le c n^{1/4}$ that appears elsewhere in the answers. This can work only when we are looking for a factorization into two close factors. If it works for a given odd $n$, it will produce a factorization into two factors whose difference is minimal and less that $2cn^{1/4}$, and it will only work for such $n$. 
A: If $\rm\ n = p\:q\ $ is a product of two "close" primes, i.e.  $\rm\:|p-q| < n^{1/3},\:$ then $\rm\:n\:$ can be factored in polynomial time, see Robert Erra; Christophe Grenier. The Fermat factorization method revisited. 2009. See also their slides How to compute RSA keys? The Art of RSA: Past, Present, Future.
A: The fastest factorization method is Number Field Sieve (NFS). To factor a 1024 bit integer $N$, it takes around $2^{86}$ many steps. 
A: well it all depends on the gap between the two consecutive primes. For twin primes, it's really easy but for two primes with gap of 10^10,000 I suppose it is much harder.
