With a twist; your algorithm has to be less complex than O(X²) where X is the Nth prime.

Here's a hint solution in C# (XlnX, 137 chars):

public List<int> P(int n)
{      
   var r = new List<int>{2}; int i=3;
   while(r.Count<n)
      if(!r.TakeWhile(x=>x<Math.Sqrt(i)).Any(x=>i%x==0)) r.Add(i++); else i++;
}

With a twist; your algorithm has to be less complex than O(X²) where X is the Nth prime. Your solution post should include the character count and the theoretical complexity in terms of X (or N, which ~= X/ln(X) and so will usually be more efficient)

Here's a hint solution in C# (O(Xln(sqrt(X))), 137 chars):

public List<int> P(int n){var r = new List<int>{2}; int i=3; while(r.Count<n) if(!r.TakeWhile(x=>x<Math.Sqrt(i)).Any(x=>i%x==0)) r.Add(i++); else i++; }