A very long hallway has 1000 doors numbered 1 to 1000; all doors are initially closed. One by one, 1000 people go down the hall: the first person opens each door, the second person closes all doors with even numbers, the third person closes door 3, opens door 6, closes door 9, opens door 12, etc. That is, the n th person changes all doors whose numbers are divisible by n . After all 1000 people have gone down the hall, which doors are open and which are closed?