[C++] 백준 1929 : 소수 구하기
#include <iostream>
int main(int argc, char **argv){ // 소수 - 에라토스테네스의 체
int M, N;
int a[1000001];
scanf("%d %d",&M,&N);
//소수 판별 범위까지 배열 생성, 값 넣어주기, 해당 수의 배수인 것 하나씩 지워나가기
for(int i=2; i<=1000000; i++) {
a[i] = i; // 배열 초기화 (인덱스의 숫자로)
}
for(int i=2; i<=1000000; i++) {
if(a[i]==0){
continue; // 이미 지워진 수 -> 건너뛰기
}
for(int j=2*i; j<=1000000; j+=i) { // 지워진 수 아닌 경우(소수) -> 배수 전부 지우기
a[j] = 0; // j의 첫번째 배수에서 수 끝까지, j = j + i (다음 배수 i만큼 더하는 것과 같다)
}
}
for(int i=M;i <= N;i++) {
if(a[i]!=0) {
printf("%d ", a[i]); // 소수 출력
}
}
return 0;
}
오늘의 키포인트
-
에라토스테네스의 체는 배열을 이용하여 소수를 구하는 알고리즘이다.
-
소수 판별 범위까지 배열을 생성하고 인덱스에 해당하는 값을 넣어 초기화해준다.
-
2부터 순회하면서 만약 배열의 값이 0 (지워진 상태)이 아닌 경우 소수로 보고 해당 수의 배수를 모두 지운다(배수이면 소수가 아니다)
Author And Source
이 문제에 관하여([C++] 백준 1929 : 소수 구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@lamknh/C-백준-1929-소수-구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)