문제가 직각삼각형 형태로 2부터 1000까지의 자연수 중 소수를 15까지 순차적으로 저장하는 문제인데요
소수를 찾을 때 홀수만 찾는 반복문을 돌리고, 홀수가 소수인지 판단하는 반복문이 있습니다.
1번 정답이 tmp[q]인데 tmp[1]도 정답으로 쳐주나요?
어떤 홀수던 3으로 나눠서 0이 아니면 소수가 되지 않나요?
해설에는 이부분에 대해 자세히 안나와서있어서, 정답이 아니라면 해설 부탁드립니다.
안녕하세요 길벗수험서 운영팀입니다.
간단히 25를 예로 들죠.
말씀하신 그대로 25는 홀수이고, 3으로 나눴을 때 나머지가 1이지만 소수가 아닙니다.
5로 나눠지기 때문이죠.
코드로 구현되는 소수 알고리즘은 정해져 있습니다.
n까지의 숫자에 대해 소수를 구한다면
1. 2부터 n-1까지의 수로 나눠 나머지를 체크한다.
2. 2부터 n/2까지의 수로 나눠 나머지를 체크한다.
3. 2부터 루트n까지의 수로 나눠 나머지를 체크한다.
4. 2부터 n미만의 소수로 나눠 나머지를 체크한다.
이 정도가 있으며 증가식을 +2로 둬 홀수만 체크하는 것은 위의 4가지 방법에 추가되는 옵션 정도에 지나지 않습니다.
행복한 하루되세요 :)
-
관리자2021-07-05 16:13:55
안녕하세요 길벗수험서 운영팀입니다.
간단히 25를 예로 들죠.
말씀하신 그대로 25는 홀수이고, 3으로 나눴을 때 나머지가 1이지만 소수가 아닙니다.
5로 나눠지기 때문이죠.
코드로 구현되는 소수 알고리즘은 정해져 있습니다.
n까지의 숫자에 대해 소수를 구한다면
1. 2부터 n-1까지의 수로 나눠 나머지를 체크한다.
2. 2부터 n/2까지의 수로 나눠 나머지를 체크한다.
3. 2부터 루트n까지의 수로 나눠 나머지를 체크한다.
4. 2부터 n미만의 소수로 나눠 나머지를 체크한다.
이 정도가 있으며 증가식을 +2로 둬 홀수만 체크하는 것은 위의 4가지 방법에 추가되는 옵션 정도에 지나지 않습니다.
행복한 하루되세요 :)