We study complexity characteristics of a Boolean function related to a natural number theoretic problem. In particular we obtain a linear lower bound on the average sensitivity of the Boolean function deciding whether a given integer is square-free. This result allows us to derive a quadratic lower bound for the formula size complexity of testing square-free numbers and linear lower bounds on the average decision tree depth. We also obtain lower bounds on the degrees of exact and approximative polynomial representations of this function. The results are based on some number theoretic results about the distribution of square-free numbers with some fixed digits (obtained by a sieve method). Using a different, yet completely elementary, method we show that neither these problems nor primality testing belong to the class AC^o[p] for any prime p.