一道关于C语言的题目

Question

Moxin为了给小王缓和心情，给小王买来了n个开关，给小王降压，但是小王的强迫症发作了，如果小王按了某个数都会把这个数的倍数全按一遍，比如按了2就会把2,4,6,8全按一遍，一个开关被按一下就会改变状态，一开始所有的开关都是关闭的，小王从1开始按到了n（按的时候按照，先把所有的倍数按一遍，比如按完了2的所有倍数，接下来就按3的所有倍数），请问有几个开关是打开的？

Input
给出一个n（文件里多组数据）1<=n<=10^9

Output
给出开着的灯的数量

SampleInput
2
SampleOutput
1

Answer 1

这就是个算法题
两个思路
1.就根据题意，模拟他按键的顺序，双重for循环，按完数一数
2.每盏灯按序号先因式分解，如果因子是奇数，它就亮；如果是偶数，那抵消了，不亮。