When I have 10 computers, the factorization of a number doesn't scale along. I am not sure how much faster it would go compared to a single computer, but not 10 times faster like one would expect.
Can someone think of another algorithm where its hard to spread the workload between different machines? Or is this an unique property of factorization?
A short search turned up this page http://en.wikipedia.org/wiki/P-complete on wikipedia, which seems to imply that proving something is hard to parallelise is non-trivial in possibly a similar way that NP$\neq$P is hard. Some problems which are thought to be hard to parallelise though, seem to be for example Horn-satisfiability or linear programming.
A problem which is easier to understand but not known to be P-complete would be GCD and extended Euclidean algorithm.