인프런 커뮤니티 질문&답변

소수란 약수가 1과 자기 자신뿐인 자연수 

여기서 약수란 말이 나오기 때문에 약수가 뭔지 알아야 겠죠. 쉽게 말해서 나누어 떨어지는 수라고 생각하면 됩니다.

즉 다시 풀어서 설명하면 나누어떨어지는 수가 1과 자기자신 뿐인 자연수
가령 10을 보겠습니다.

10은 나누어떨어지는 수(약수)가1과 10(자기자신) 뿐인가요?
아니죠, 10은 2로도 나누어떨어지고, 5로도 나누어떨어집니다. 1, 2, 5, 10 이 10의 약수가 되겠네요
나누어 떨어진다는 말은 다시말해 나머지가 없다는 말과 같습니다.

즉 문제의 정의를 다시 생각해보면
가령 10의 소수의 개수를 찾아? 소수를 찾아라? 라고 한다면
1과 10 이외의 숫자로 나누어 떨어지는 것(약수)이 있는 지 확인해보면 되겠죠?

또한 왜 n/2 까지만 반복문을 돌리냐?
그 원리는 간단합니다. 

10의 약수는 1, 2 , 5, 10 
18의 약수는 1, 2, 3, 6, 9, 18 

보시면 알겠지만 전부 짝을 이룹니다. 1 * 10 = 10, 2*5 = 10, 1 * 18 = 18, 2*9 = 18, 3*6 =18
10의 중앙 10/2 = 5 를 기점으로 그전에 있는 수로 나누어 떨어지는 지 떨어지지 않는 지만 체크해도 충분하기 때문입니다.
그렇기 때문에 문제에서는 i < n  이 아닌 i < n/2 를 사용하고 있는 것입니다.  i < n 해도 아무런 지장은 없습니다.