소수의 개념을 알겠지만 원리를 모릅니다.. 그냥 외워야 할까요?

Question

1이랑 또 다른 숫자하나? 정도로 소수를 정의하고 있습니다 수학적으로 n/2 이런거 이해가 안갑니다.. 그냥 소수찾을때 공식처럼 외워서 사용해도 되는 걸까요? 문과라.. 휴 어렵네요

Gg G · Answer

소수란 약수가 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 해도 아무런 지장은 없습니다.