컴공 일기 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를 선물하세요.
-
Vaundy 내한해라
-
수험생 -> 수능 1달남아서 공부해야함 대학생 -> 중간고사 기간이라 공부해야함...
-
의대가고 싶어서 반수를 할까 고민을 했는데 결국 의지가 부족하기도 하고 성적도...
-
팀 이쁨? 1
미페 맛도리임
-
인중 3
인증 말고 인중으로 봤으면 화작 합격
-
작년엔 적생모 적중예감같은 인강컨 했었고 올해는 서바만 주구장창 풀고 있는데 계속...
-
똥 발싸! 히히
-
그냥 나타낼 수 있는 좌표를 다각도에서 다 쓴 다음 치환 연립 할 거리 찾아서...
-
사탐 기출만 3
돌려서 1등급 맞을 수 있을까요? 정법은 3등급이 목표고 사문은 1등급이 목표인데...
-
연논재시험보면 1
기차타고또가야하나돈아까운데
-
건강관리를 지금부터해서 오래오래 사는걸로 기만해야겠음,,,, 나중에는 건강한게 자랑거리다 이겁니다
-
ㅇㅈ 3
학교다닐때 아스날경기 맨날 강의실에서 봄
-
휴 0
열품타 순공시간 갤럭시 워치로 기록하기 4000원 주고 샀다...
-
다들 머리도 좋고 수능에 관해선 모르는 게 없을 것 같은데
-
. 1
-
화난 이유는 없음 갑자기 화가 날 뿐
-
이거 미분 좀 해주세요 11
아무리 미분해도 해설지처럼 안되는데 세 함수의 곱미분느낌으로 보고 계산해야하나요?...
-
각변환이거 0
그냥덧셈정리쓰고해결하는데 각변환안쓴지1년도넘은듯
-
정법 질문 2
위헌심사형 헌법소원을 헌재에서 인용하면 위법심처럼 재판이 일시 정지되나요…?
-
3시 시험이고 4
1교시 수업있음 1교시는 걍 교양 수업임 3시에 전공셤인데 이제 1회독함… 밤…새야겠지?
-
응 다들 화이팅하자
-
기만러들 격추시키게
-
씹년 아니 쭈인님아 ㅈㅂㅈㅂㅈㅂㅈㅂ 부상좀 그만좀 쳐 당하세요 또 누울꺼는 어처피...
-
혹시 글쓰기 수정에서 첨부파일을 다른 것으로 바꾸려고 할 때 0
혹시 글쓰기 수정에서 첨부파일을 다른 것으로 바꾸려고 할 때 어떻게 바꾸시는지...
-
나는 수능만 치면 살빠짐 올해 안 치니까 돼지네 깨달음
-
틀릴까봐 2번씩 검산하는 게 습관임 ㅠㅠ
-
인증메타 누가 멈춰주세요
-
어케햇지…
-
맞다면 1시간만 미뤄줘요 아직 공부가 안 끝났어
-
뭔가 이거 나올거같은데 통수의 달인답게 옥루몽 옥린몽 유씨삼대 조웅 조까하고 이거 나올거같음
-
한강작가책 2
이번에 중고로 구입가 3배에 팔아서 재미좀 봄,,,,
-
인증 6
이 궁금하신가요?
-
몸이 이상했음 지금보다 몸무게 7키로는 덜 나가는데 살찐비만이었음 밥을 거의 안...
-
프로필 사진을 수능 접수 사진이랑 연동시켜주세요
-
아가 자야징 2
바이바이
-
내가 지금 살이 찐 상태라 꼭 그래야만 함
-
이럴 때면 또 갑자기 여르비가 나타남. 평소에도 눈팅러 중에 여르비 꽤 있을 듯
-
1~10번 1개 정도 틀리고 3점 다 맞춤 확통 3점짜리만 다 맞춘
-
콤부차 0
탄산음료 대용으로 마시면 문제생기나
-
중간에 병원 다녀옴 색칠하는 거 불편한데 열품타로 옮길까요
-
번따당했는데 사이비였어요 jms?였나..
-
계속 안해야지
-
ㅇㅈ메타네 4
골 차로 패배하는 맨유
-
용도가 뭐임
-
ㅋㅋ나만못생김 12
괜찮아..
-
다들 수고하셨습니다!
-
그리고 짜피 재탕임 건질사진도없어..
군대에서 코딩은 어떤 앱으로 하고 계신가요?