Fluctuating readings of LM35 temperature sensor (+- 5°C) with Arduino UNO
The cause is the low sinking capabilities of LM35 output. This makes the output sensitive to EMI. Yes, the output output impedance is stated as 0.5 ohms but only for sourcing current. The sinking current is limited to 1uA which is easily achieved by the environment noise. 


You need to add a low impedance load between LM35 output and ground, can be 200 ohm as the data sheet recommends for heavy capacitive loads but I wouldn't go that far, might be 1k or 2k to avoid self heating errors. 

No software only solution can solve this error.