Prime factorization in a functional language

I'm writing in OCaml, trying to give a (somewhat) efficient implementation of prime factorization. I figure the best representation of a number 2 or more is in a list of exponents. For simplicity with consing I'll do it in decreasing order of primes. So 2 would be [1] and 3 would be [1;0] and 4 would be [2], and 5 [1;0;0].

I was thinking of using the sieve idea to take a number n and look for all possible divisors between 2 and sqrt(n). Then divide by any divisor and recurse. However, every implementation that I can think of seems to involve repeatedly searching over a list and that seems just unnecessarily inefficient. The outline of my solution is best stated in this code

let rec pf n =
  if (n=2) then ([1], 0)
  else let sq = int_of_float ( (float_of_int n) ** 0.5 ) in
  let primes = getPrimes sq in
  match earliestDiv n primes with
  | None -> n::(zero_list (n-1))
  | Some (x, i) -> let subproblem pf (n/x) in
              increment subproblem i

The helper functions here would be:

• getPrimes which takes an int and returns a list of all prime numbers less-than-or-equal to it.
• earliestDiv which takes an int n and list of ints lst, returns an int*int option corresponding to the earliest number in lst which divides n. That will be the first coordinate of the tuple; the second coordinate will return the index of this prime x in the list of primes.
• increment will take an int list and index, and increase by 1 the number located at the index.

All of these helper functions keep making lists, and passing through lists, and so on. And in fact, I often feel like I'm doing this in functional programming. I often have the sense that I'm unnecessarily iterating over lists whereas in imperative languages I would be writing code that is more efficient. Perhaps it's just in my head, and when writing in imperative languages I less often notice how many resources are going into some of the list operations I use. But if I'm missing some important technique that could prevent repeatedly scanning lists, I'd be curious to hear it.

The question: Is it necessary to repeatedly make and iterate over lists in order to write this function?