// LockerProblem.java
// Written (mostly) in class on Tue 6-Oct-09

import java.util.*;

public class LockerProblem {
  
  private static final Random random = new Random();
  
  public static boolean[] lockerProblem(int lockers) {
    // Need an extra locker because we will IGNORE locker 0
    boolean[] lockerIsOpen = new boolean[lockers+1];
    int students = lockers;
    for (int student=1; student<=students; student++) {
      for (int locker=student; locker<=lockers; locker+=student)
        lockerIsOpen[locker] = !lockerIsOpen[locker];
    }
    return lockerIsOpen;
  }
  
  public static void main(String[] args) {    
    System.out.print("Enter number of lockers: ");
    Scanner scanner = new Scanner(System.in);
    int lockers = scanner.nextInt();
    boolean[] lockerIsOpen = lockerProblem(lockers);
    System.out.print("Here are the open lockers:\n  ");
    for (int locker=1; locker<=lockers; locker++)
      if (lockerIsOpen[locker])
        System.out.print(locker + "  ");
    System.out.println();
  }
}