It does not. There are many factorization algorithms that are significantly faster than trial division for large numbers (http://mathworld.wolfram.com/PrimeFactorizationAlgorithms.ht...)
And your description makes little sense to me. I guess it is based on a bad understanding of RSA (http://en.wikipedia.org/wiki/RSA_%28algorithm%29). That does not convert your message to a prime.
Read the description again then, RSA is a public key algorithm, and is not what I am describing.
Size is key though. A rough guide of the GNFS times for a quad core PC would give:-
c100 - c120: hours
c120 - c140: days
c140 - c160: weeks
c160 - c180: months
c180 - c200: years
For comparative sizing:-
2^256 =~ c80
2^512 =~ c160
2^1024 =~ c320
Part of the hard work in choosing random primes to use within such encryption algorithms is avoiding numbers which are susceptible to each of those algorithms, e.g. avoiding primes with simple p-1 factorisations to avoid being susceptible to Pollard's P-1 algorithm.
The wrong choice of prime and the factorisation becomes (relatively) trivial.
I'm not sure how a modern CPU would do, but I suspect on the low end of "weeks".
A few months to crack a 45 bit encryption doesn't sound quick to me. Even a 64 bit encryption would take many centuries at that rate.