티스토리 뷰
소수찾는 문제에 자주 나오는 알고리즘이므로
한 번 정리 해두려 한다
여긴 복붙이라 봐도되고 밑으로 내려도된다
- 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
- 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
- 자기 자신을 제외한 2의 배수를 모두 지운다.
- 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
- 자기 자신을 제외한 3의 배수를 모두 지운다.
- 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
- 자기 자신을 제외한 5의 배수를 모두 지운다.
- 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
- 자기 자신을 제외한 7의 배수를 모두 지운다.
- 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.
그림의 경우 11^(2)>120 이므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.
정리하자면
n을 입력받아
1~n중에 소수를 알고 싶으면
2,3,5,7 ... i*i<=n 을 만족하는 i까지의 소수들 중
자기 자신을 제외한 배수를 모두 false로 처리한다
그렇게 되면
true인 값들은 소수로 판별할 수 있다
이렇게 말하면 뭔소린지 잘 이해가 안되니까
코드를 보면서 이해하자
void Eratos(int n)
{
/* 만일 n이 1보다 작거나 같으면 함수 종료 */
if (n <= 1) return;
/* 2부터 n까지 n-1개를 저장할 수 있는 배열 할당
배열 참조 번호와 소수와 일치하도록 배열의 크기는
n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음) */
bool* PrimeArray = new bool[n + 1];
/* 배열초기화: 처음엔 모두 소수로 보고 true값을 줌 */
for (int i = 2; i <= n; i++)
PrimeArray[i] = true;
/* 에라토스테네스의 체에 맞게 소수를 구함
만일, PrimeArray[i]가 true이면 i 이후의 i 배수는 약수로 i를
가지고 있는 것이 되므로 i 이후의 i 배수에 대해 false값을 준다.
PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시
소수가 아니게 된다. 그러므로 검사할 필요도 없다.
또한 i*k (k < i) 까지는 이미 검사되었으므로 j시작 값은 i*2에서 i*i로 개선할 수 있다.
*/
for (int i = 2; i * i <= n; i++)
{
if (PrimeArray[i])
for (int j = i * i; j <= n; j += i)
PrimeArray[j] = false;
}
// 이후의 작업 ...
}
배열을 n+1 인덱스 까지 할당하고
전부 true로 초기화 해준다
일단 모두 소수로 본다
그 후에 일련의 과정을 거쳐 소수가 아닌 것들은 false로 바꿔
나중에 true인 것들만 출력하면 그게 소수들의 집합이다
for(int i=2; i*i<=n; i++)
이 코드를 보면
i*i<=n이게 핵심이다
n이 만약 120으로 주어졌다면
i=2~120까지 반복문으로 확인할 필요가없고
i=2~10까지 확인하면 된다(배수를 다 false로 처리하기때문에)
왜냐하면 11*11>120이므로
11보다 작고 2보다 크거나 같은
2~10 까지에서의 소수의 배수들만 처리하면
2~120을 일일히 처리하는 것보다
중복을 최대한 줄일 수 있다
다음으로
if (PrimeArray[i])
for (int j = i * i; j <= n; j += i)
PrimeArray[j] = false;
}
이 코드에서
if(PrimeArray[i])
즉 소수인 수만 진행한다는건데
소수가 아닌 수 만약 i=4이면
이미 i는 2일때 4는 false로 처리됐을거다
4의 배수 8,12,16...은 이미 2의 배수가 다 false로 처리했다
그러니까 소수가 아닌 값들은 그 값들의 배수들도 이미 false로 처리가됐을거기때문에
중복되는 일을 막기 위한 것이다
for(int j=i*i; j<=n; j+=i)
이 코드에서 j=i*i로 시작하는 이유는
j의 배수 중 i*i 이하의 수는 이미 false로 처리됐기 때문이다
예를들어
i=5일때 5, 10, 15, 20, 25를 보면
10,20은 이미 2의배수에서 false로
15는 3의배수에서 false로 됐다
처음 true로 설정된 값은 i*i부터이다
그래서 i*2로 시작하는것보다 더 효율적이다
1929번 코드
#include <iostream>
#include <math.h>
using namespace std;
void Eratos(int,int);
int main() {
int m, n;
cin >> m >> n;
Eratos(n, m);
return 0;
}
void Eratos(int n,int m) {
bool* PrimeArray = new bool[n + 1];
for (int i = 2; i <= n; i++)
PrimeArray[i] = true; //처음엔 모두 소수로 봄
PrimeArray[1] = false;
for (int i = 2; i * i <= n; i++) { //n에 루트씨운거 이하의 값들 중
//소수만 판별해도 됨
//예를들어 n이 120이면
//11*11>120 이므로
//11보다 작은 수의 배수들만 지워도 된다
if (PrimeArray[i]) { //PrimeArray[i]가 false이면
//i는 이미 소수가 아니므로 i의 배수 역시 소수가 아니게 된다
//그러므로 검사할 필요도없다
for (int j = i * i; j <= n; j += i) { // i*k(k<i)까지는 이미 검사되었으므로
//j의 시작값은 i*2에서 i*i로 개선할 수 있다
PrimeArray[j] = false;
}
}
}
for (int i = m; i <= n; i++) {
if (PrimeArray[i])
cout << i << "\n";
}
}
내가 겪었던 출력초과, 시간초과오류
출력초과는 배열 초기화를 0~n까지 하지 않고
m~n까지 했을때 나타났다
시간초과는
cout<<arr[i]<<endl;을
cout<<arr[i]<"\n";으로 바꾸어주니
해결됐다
이게 참 어이가 없었는데
출력 다 잘되는데 시간초과가 떠서 뭐가 문젠가 했더니
이 한줄바꾸니 됐다
이건 뭐..진짜 질문아니었음 몰랐을듯
endl보다 "\n"이 더빠르다는 걸 알게됐다 왜지?ㅋㅋㅋㅋㅋㅋ
그리고
배열을 new로 할당해주고
초기값이 당연히 true일거라 생각했는데
초기화를 해주어야핸다는 것을 이번 문제를 통해 알게되었다
'코딩 테스트 > 백준' 카테고리의 다른 글
백준 10989 counting sort c++ (0) | 2022.01.19 |
---|---|
백준 2751번 merge sort c++ (0) | 2022.01.18 |
백준 1018 c++ (0) | 2022.01.13 |
백준 2231 분해합 c++ (0) | 2022.01.12 |
백준 1712번 c++ (0) | 2021.12.27 |
- Total
- Today
- Yesterday
- 인프콘2024
- git 예전 커밋 수정
- authorization code
- git
- oauth
- html #웹 #웹사이트 #플레이리스트
- CSS
- DDL
- 클로아
- DML
- infcon 2024
- Android Studio
- 프로그래머스
- 로스트아크 캐릭터
- 데이터3법
- kloa
- SQL
- 데이터베이스
- 우분투
- 2024인프콘
- authorization_code
- git commit 수정
- SpringBoot
- 리눅스
- oauth2.0
- 오픈소스
- javascript
- html
- bfs
- 데이터 3법
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |