Pseudo-polynomial time algorithms
I think this somehow “uneasy feeling” comes from the fact that human beings consider natural numbers only with a semantic—if I see 2001, e.g., I immediately think of 9/11 or Stanley Kubrick or something, that is, you interpret the number. In terms of inputs for an algorithm, however, it is merely a string of characters, and could just as well be such nonsense as ¨*^! or anything. What we as algorithm analyzers care about is only the length of the string, and absolutely not what it contains or represents. You really have to get this into your mind because otherwise you could e.g. say that $PRIMES$ is obviously in $\mathsf{P}$ as you can just try to divide a number $x$ by all numbers between 1 and $x,$ and this algorithm has obviously polynomial runtime. I hope you see the pitfall.