How many times for reboot?

If you format disk and install a new windows, it will install many patches that requires multiple restart. Usually less than 10 times after a fresh windows would be OK.

Anything else, ... did you really format your disk?