컴공 일기 246
… 예… 오랜만에 들어와서 요새 풀고 있는 알고리즘 코드 하나 올려놓고 갑니다…
여전히 꽤…는 아니어도 열심히는 사는 중입니다…
간단한 해설을 하자면 소수를 찾는 알고리즘입니다.
주로 Sieve of Eratosthenes, 에라토스테네스의 체라고 얘기합니다. 컴퓨터에서 소수를 찾는 여러가지 방법이 있습니다만, 학부 수준에서 가장 이해하기 쉽고 직관적인 알고리즘이라고 할 수 있겠네요.
소수가 아닌 게 확실한 수를 지워나가는 방식입니다. 그래서 ‘체’라는 말을 쓰죠. 걸러낸다는 거예요.
그럼 뭘 걸러내면 될까요? “배수”들을 걸러내는 겁니다.
2의 배수, 3의 배수, 4의 배수, 5의 배수, 6의 배수…. 등등 전부요.
예를 잠깐 들어볼까요? 만약에 1부터 100까지의 자연수 범위에서 소수를 찾고 싶으면, sqrt(100) 즉 10의 배수까지 다 지워내면 됩니다. 어? 100까지니까 100의 배수까지 지워야 되는 게 아니냐고요?
사실 맞습니다만, 10의 배수까지만 탐색해도 전부 탐색할 수 있습니다. 만약 N이 소수가 아니라서 a * b의 형태를 이룬다면 즉, N = a * b 라면, a와 b의 최댓값은 루트 N입니다. a와 b는 모두 자연수이기 때문이지요. 만약 둘 중 한 수가 루트 N을 초과하는 순간, a * b의 값은 N을 넘어서게 됩니다. 따라서, 루트N까지 탐색의 범위를 제한해도 무방합니다.
에라토스테네스의 체는 이중반복문으로 구현이 되어서 얼핏 O(N^2)의 부담스런 시간복잡도를 가지는 듯 하지만,
실상은 그렇지 않습니다. 왜냐하면 대다수의 경우가 if(prime[i] == 0) continue;를 충족시키기 때문이지요…
말하자면 그 전에 지워낸 게 많아서, 새로운 배수에서 소수가 아닌 수를 지울 때, 탐색해야 할 후보군이 많이 없다는 뜻입니다.
그 효율성 때문에 알고리즘 문제에서 자주 이용된다.. 뭐 그리 생각하면 됩니다.
오늘도 재미있는 공학 시간..
#include <iostream>
#include <cmath>
#define MAX 1000001
using namespace std;
int prime[MAX];
int n, a, b, result;
int main()
{
cin.tie(NULL);
ios::sync_with_stdio(false);
for(int i=2; i<MAX; i++)
{
prime[i] = i;
}
for(int i=2; i<sqrt(N); i++)
{
If(prime[i] == 0) continue;
for(int j=i * i; j < MAX; j+=i)
{
prime[j] = 0;
}
}
while(1)
{
cin >> n;
if(n == 0) break;
for(int i=3; i < MAX; i++)
{
if(prime[i] != 0)
{
if(n - prime[i] != 0)
{
a = i;
b = n - prime[i];
break;
}
}
}
cout << n << " = " << a << " + " << b << "\n";
}
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
수특 수완 다 끝냈고 기출책은 따로 수능 기출의 미래라는 책 풀었는데 이제...
-
ebs넘어가도 되나요? 당연히 안되겠죠?
-
수능 앞다리가 1이라는데 아닌데요 앞자리가 6이에요가 아니라 지금 수능 전나리었지...
-
초코우유 원탑은? 둘다 먹어보신 분만 투표 부탁드려요 ㅎㅎㅎ
-
수능때 3,4등급 목표면 노베인 사문하기보다는 생2 유지가 나음? 사문이 2달하면...
-
1. 개어렵지만 경쟁률 낮은 숙대 2.비교적쉽지만 경쟁률 높은 동국대나 세종대
-
과탐러들아 걱정 좀 하지마라 대학들이 병신이냐? 뻔히 과탐러들이 지능도 높고...
-
이원준T 9평 해설 특강 신청햇는데 자리예약 따로 안해도 대나요? 현강을 가본 적이...
-
국어특 6
시간은 남는데 채점하면 엄..
-
과탐 5~6등급이 능지문제일 가능성도 있지만 과학에 흥미가 없음>>공부를...
-
지금부터 하루에 하나씩 수학 실모 푸는거 어케 생각하시나여 8
9평 68점...(확통 1틀)이고 6시 이후로는 수학만 할까 생각입니다 국영탐으로...
-
싸우지마세용 22
친하게 지내용
-
사탐런 안하면 고인물들만 남아서 컷 높아지고 피해 볼 수도 잇는거임..?
-
전국 의대 전국 치대 전국 한의대 전국 약대 전국 수의대 서울대 자연계열 전부...
-
그래? 알엔디 한번 삭감했더니 문과에 인재들이 몰리네!
-
언미물2화2러
-
고민임 원래는 교대 가고싶었는데 요즘 워낙 말이 많아서.. 6모는 서성한 낮과 9모 연고 낮과 나옴
-
수험커뮤에서 공부 관련 글은 반응없고 사과탐 갈드컵만 하루종일
-
병신이 틀림없다 뒤에 계산은 다 맞네
-
9모 영어 3등급 받았는데 빈칸이랑 순삽 풀 시간은커녕 준킬러 문제들도 푸는 데...
-
지2 기출 질문 0
지금 좌표계~일주 연주운동 파트 완강했는데 이쪽 기출을 풀고 다음파트로 가나요...
-
불수능 제발 내줘 오히려 좋아 이런소리 하는 사람들 실제로 불수능 나오면 수능끝나고...
-
내년수능때 안정적으로 1등급 받고싶은거면 생윤은 걍 안하는게 맞나요? 재밋어서...
-
방금 오르비 글 내리다가 봤는데 이게 진정한 문이과 통합형 인재지 ㅋㅋㅋㅋㅋ
-
둘다붙으면 어디가심?
-
방금 접수했는데, 11만 5천번대
-
만년 3등급인데 4규같은거 벅벅 푸는거밖에 답없나요
-
생1 3등급 지1 2등급 vs 생윤사문 둘 다 1등급 3
입결만 보고 원서 쓴다 그럼 님들 같음 뭐 고르나요
-
이번 9모때 처음으로 안정액 먹고 응시 했는데 아침 7시40분 한병 점심 먹고...
-
실모치면 언어보다 매체를 더틀리는 놈인데 화작을 그 매체의 두배를 틀림
-
맞팔구 4
똥테기념
-
둘 다 합격하면 어디 가시나요?
-
그만큼 사탐런이 사기란거임 이게 수능성적이라 생각해보셈ㅜㅜ 근데 나 ㄹㅇ 어캄?
-
2등급이상은 받아야하는구나...
-
절대 내가 잘 본 시험이어서 그런 게 아님 21처럼만 나와다오
-
4등급따리입니다... 25번은 인강에서 설명을 안해줘서 댓글로나마 풀이법...
-
투투가 나을수도 5
투가 괜찮아서가 아니고 원이 박살났기 때문 가산이라도 받아라
-
오르비에서 논란이 많다보니 비판갤도 활성화되네요...ㅋㅋㅋㅋ 소신)다른건몰라도...
-
ㅂㄹ임요..? 네이비색인데 대학 로고있음..
-
사탐으로 밀고들어와도 별 타격없는 쌍윤러들 우리 올해 꼭 50 50 가자 우린...
-
내 동생이 9모 과탐 3등급 포함 그 밑이다? 뒤통수 갈기고 재접수 시키러 끌고감
-
상상등급컷 0
어떻게 생각함 난 아무리 생각해도 5-1이 언매 82라는게 이상해보이는데
-
주문 완료...다시 달려보자
-
예전에 0
나형 시험지가 이랬음?
-
모교 방문함 8
이젠 경비원 아저씨도 바뀌었고 청소부 아주머니만 계시네요. 그나저나 남정네들...
-
사탐런 안한이유 0
개념조차도 끝낼시간이 없음.. + 홍논최저는 사1과1안된다던데 ㅋㅋㅋㅋ
-
미인정처리로 조퇴하고 싶다고 오늘 쌤한테 말씀드렸는데 1학기때 학교 선생님 추천으로...
-
투표해주세여
군대에서 코딩은 어떤 앱으로 하고 계신가요?