Most people agree with your statement in general, but it's still an open question. I used to have an interest in prime numbers, and I would like to point out a couple of things that you may not be aware of.
From Integer factorization - Wikipedia :
No algorithm has been published that can factor all integers in polynomial time, that is, that can factor a b-bit number n in time O(bk) for some constant k. Neither the existence nor non-existence of such algorithms has been proved, but it is generally suspected that they do not exist and hence that the problem is not in class P. The problem is clearly in class NP, but it is generally suspected that it is not NP-complete, though this has not been proven.
I copy-pasted this text from the middle of a wikipedia entry because I feel like they explain it better than I can. Basically P <= Integer Factorization <= NP, but P and NP may or may not be equal. Most people believe that P != NP because a lot of smart people have written algorithms to solve NP-complete problems and weren't able to solve them in polynomial time. On the other hand, a lot of even smarter people have tried to prove that P != NP, and they all have failed.
What that says to me is that no one has a good answer. I'd like to point out that I can't think of a polynomial time algorithm that's slower than O(n^3). If no one's ever written a O(n^15991) algorithm, how can anyone say anything about what a such an algorithm might be able to do? No human could ever write such an algorithm, but maybe there's some loophole that lets such an algorithm solve integer factorization problems.
I can beat the algorithm you described in two different ways that I already know about.
First, you only go up to square root of n [which I'll call sqrt(n)], not n/2.
Assume n = a * b for some a and b. We may assume without loss of generality that a <= b. (This just makes this text simpler. One of them <= the other. It doesn't matter which.) If both a and b were less than sqrt(n), then a * b < n. If both a and b were more than sqrt(n), then a * b > n. So a <= sqrt(n) <= b If n has any factor other than 1 or n, it must have a factor <= sqrt(n). If that factor is composite, then it has a prime factor even less than it. So any composite number has a prime factor less than or equal to sqrt(n). So we only need to check prime numbers less than or equal to sqrt(n).
Second, it's possible to combine primes, reducing the number of trial divisions (though typically at the cost of memory).
For instance, let's look at 2 and 3. Their product is 6. When you divide any number by 6, you get a remainder.
Remainder Divisible by
0 6
1 Neither 2 nor 3
2 2
3 3
4 2
5 Neither 2 nor 3
This works because of modular arithmetic, but I'm not going to explain beyond that. You could multiply more than 2 prime numbers together or use multiple sets of pairs of primes. This hasn't produced a significantly better solution, but there's other options beyond what you describe.
Another similar problem, primality testing, used to be solved in the same manner. But a better solution has been found. The AKS primality test - Wikipedia runs in polynomial time.
Maybe something similar will happen with integer factorization. Or maybe the boundary between polynomial and exponential just happens to be between primality testing and integer factorization.
Edit: Fixed the quotes slightly.