소수를 구할때 만약에 5가 소수임을 구하려면 1,5를 제외한 나머지 2,3,4 숫자중에서 나눠 떨어지는 수가 하나도 없으면 소수인 것이라고 알고 있습니다.
44번 문제에서 double t = Math.sqrt(n);라고 소수인지 확인하려는 숫자의 제곱근을 구해서 2부터 제곱근 숫자까지 나눠 떨어지는 수가 없으면 소수로 확정하는 코드를 작성하고 있습니다.
여기서 왜 제곱근까지만 나눠보는 것인지 궁금합니다. 강의를 들어도 잘 모르겠어요ㅠㅠ
안녕하세요 길벗수험서 운영팀입니다.
20이 소수인지 판별하기 위해서는 20을 나눴을 때 나머지가 없는 약수가 1과 자기 수(20) 외에는 없어야 합니다.
20보다 작은 수인 19까지 비교를 시작해보죠
1*20
2*10
4*5
5*4
10*2
이때 5*4부터는 이전에 수행한 연산 4*5와 겹침을 알 수 있습니다.
10*2도 2*10과 겹치죠.
이런 겹쳐지는 경우의 수를 가능한 줄여서 연산을 최소화한 것이 '제곱근'까지만 연산을 수행해보는 것입니다.
20의 제곱근은 4.??? 입니다. 4라고 치고 1~4까지만 약수가 있는지 확인해보면 20이 소수인지 판별할 수 있게 되는 것이죠.
행복한 하루되세요 :)
-
관리자2022-04-27 11:25:25
안녕하세요 길벗수험서 운영팀입니다.
20이 소수인지 판별하기 위해서는 20을 나눴을 때 나머지가 없는 약수가 1과 자기 수(20) 외에는 없어야 합니다.
20보다 작은 수인 19까지 비교를 시작해보죠
1*20
2*10
4*5
5*4
10*2
이때 5*4부터는 이전에 수행한 연산 4*5와 겹침을 알 수 있습니다.
10*2도 2*10과 겹치죠.
이런 겹쳐지는 경우의 수를 가능한 줄여서 연산을 최소화한 것이 '제곱근'까지만 연산을 수행해보는 것입니다.
20의 제곱근은 4.??? 입니다. 4라고 치고 1~4까지만 약수가 있는지 확인해보면 20이 소수인지 판별할 수 있게 되는 것이죠.
행복한 하루되세요 :)