이 문제에서 x가 소수인지 판별하려면 x-1까지 나누어떨어지는지 확인하라는 것이 핵심인데
알고리즘에서 조건문인 J:i 부분에 소수로 빠질려면 답은 >이고 확인을 하려면 <=으로 정답이 나와있습니다.
여기서 >=과 <로 해도 무관한가요? 번거롭게 한번더 도는 경우가 생기긴하나 소수판별은 되는것 같아서 질문드립니다.
안녕하세요 길벗수험서 운영팀입니다.
예, 맞습니다.
본래 알고리즘은 i(A-1)까지 나누어떨어지는지 확인하고 J가 A가 된 순간 '소수'임이 출력하는 알고리즘이지만,
J가 i(A-1)과 동일한 경우 소수로 빠져도 알고리즘 수행에 문제는 없습니다.
(이 경우 A-2까지만 소수판별을 수행하고 A-1이 된 순간 '소수'임을 출력하겠죠)
소수를 구하는 알고리즘 자체가 사실 본인보다 작은 수까지 반복해 가며 나머지가 0인지 체크하는 방식인데,
수학식으로 따져보면 소수를 판별하려는 수(A)는 제곱근(루트A)까지만 나누는 것만으로도 해당 수가 소수인지 알 수 있기 때문이죠.
(교재 60쪽 유형3에서 나옵니다.)
행복한 하루되세요 :)
-
관리자2019-07-23 11:05:05
안녕하세요 길벗수험서 운영팀입니다.
예, 맞습니다.
본래 알고리즘은 i(A-1)까지 나누어떨어지는지 확인하고 J가 A가 된 순간 '소수'임이 출력하는 알고리즘이지만,
J가 i(A-1)과 동일한 경우 소수로 빠져도 알고리즘 수행에 문제는 없습니다.
(이 경우 A-2까지만 소수판별을 수행하고 A-1이 된 순간 '소수'임을 출력하겠죠)
소수를 구하는 알고리즘 자체가 사실 본인보다 작은 수까지 반복해 가며 나머지가 0인지 체크하는 방식인데,
수학식으로 따져보면 소수를 판별하려는 수(A)는 제곱근(루트A)까지만 나누는 것만으로도 해당 수가 소수인지 알 수 있기 때문이죠.
(교재 60쪽 유형3에서 나옵니다.)
행복한 하루되세요 :)