-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
소수구하기-백준 1929 질문
23.12.04 02:15 작성 조회수 198
0
안녕하세요 강의 너무너무 잘보고 있습니다
소수구하기 백준 1929 강의 중
for(소수의 배수값을 N까지 반복)
for (int j=i+i; j<=N; j=j+i){ }이 부분에서 for문 시작 ( j=i+i )이랑 증감식 ( j=j+i ) 이 이해가 잘 되지않아
질문 남깁니다.
그리고 저 for문은 컨티뉴일 경우에는 실행이 안되는건가요 ?(ex)4이면 컨티뉴 >> 하고 for문을 도는건가요?)
감사합니다
답변을 작성해보세요.
0
인프런 AI 인턴
2023.12.05
안녕하세요, 인프런 AI 인턴입니다.
tmdwl1110님, 소수 구하기 문제에서 언급하신 for문의 로직은 에라토스테네스의 체 알고리즘을 구현하는 부분입니다.
for문의 시작 조건인 (j=i+i)는 i가 소수인 경우, i의 배수들을 제거하기 시작하는 지점을 나타냅니다. 여기서 i+i (즉, 2*i)부터 시작하는 이유는 i의 2배수부터 i의 배수가 됨으로, 이미 i는 소수로 판별되었기 때문에 그 다음 배수부터 확인하면 됩니다.
증감식인 (j=j+i)는 j의 값을 i만큼 증가시켜 다음 i의 배수로 이동하게끔 합니다. 이는 i의 배수를 모두 찾아서 체크하는 과정을 반복적으로 수행하기 위함입니다.
continue 키워드를 만나면 그 이후의 for문 내부의 로직을 실행하지 않고, for문의 다음 반복(즉, j=j+i 이후의 다음 배수)으로 진행합니다. 즉, continue는 해당 반복을 건너뛰고 for문의 다음 반복을 계속한다는 것을 의미합니다.
소수 판별 문제에서는 continue를 사용하여 이미 체크된 배수(즉, 소수가 아닌 수)를 다시 체크하지 않도록 효율성을 높일 수 있습니다.
답변 1