The smallest prime is 2.  So we try 2:

   500
2)1001
  1000
     1

So 2 in not a factor of 1001 because it leaves a remainder of 1 when we divide 1001 by 2.

So we try the next prime, which is 3:

   333
3)1001
   999
     2

So 3 in not a factor of 1001 because it leaves a remainder of 2 when we divide 1001 by 3.

So we try the next prime, which is 5

   200
5)1001
  1000
     1

So 5 in not a factor of 1001 because it leaves a remainder of 1 when we divide 1001 by 5.

So we try the next prime, which is 7

   143
7)1001
  1001
     0

So 7 in a factor of 1001 because it leaves a remainder of 0 when we divide 1001 by 7.  

So the answer is 7.

Edwin