Your task is write a program to output How many doors are open after the last pass? Assumptions all doors are closed at first.
Input
a positive numbers n, total doors. n<=100000
Output
a positive numbers ,the total of doors opened after the last pass.
Sample Input
10
Sample Output
3
Solution:
ALGORITHM Lockerdoors(n)
//Solve the Lockerdoors problem
//Input: An positive interger n
//Output: An nonnegative interger m of the total of doors opened after the last pass
for x←1 to n do A[x] = true
for i←2 to n do
for j←i to n do
if j mod i = 0 do
A[j]←not A[j]
m←0
for i←1 to n do
if A[i] do
m←m+1
return m
这是一个比较直接的解决的算法.算法时间复杂度是θ(n^2)