컴공 일기 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를 선물하세요.
-
특히 지구과학 작년 9평 48 작수 47 올해 6평 43(공부 다시한지 1주) 올해...
-
https://orbi.kr/00065829761 ㅅㅂ 지구 나름 출제일도...
-
ㄷ이 아닌건 알겠는데… ㄴ이 왜 맞는거죠? 대다수의 사회 구성원이랑 다수의...
-
기적급으로 올린건가요? 어제 9모보고 언니랑 얘기하는데 언니가 작년 9평이랑 수능때 딱 저랬음…
-
쌩7수는 아니고.. 도움이 간절해서 제목으로 어그로 끈점 사과드립니다ㅎ 몇년만에...
-
흠 물리 진짜 좆된거같은데
-
일단 검더텅 다 끝내구(중간중간 개념 복습하면서) 그 다음 뭐하는게 맞을까요 이번에...
-
1번 엄..
-
국수 둘 다 만표 150찍을 거라 믿어 탐구도 만표 70이상 나올 거라 믿어
-
언매 35 질문 1
언매 35번에 4번 그저께 낮만큼 더웠다가 관형어인건 알겟는데 부사어가 될 수는...
-
물리 망한거임? 2
ㅋㅋㅋ 임마들 타과목은 난이도 다 올리면서 물리만 물폭탄붓는거 보면 수능도 빡세게 안할거같은데
-
9모 98점입니다 수특은 여름방학 전에 대충 한 번 풀어봤어요 거의 다 까먹은...
-
납득이 안 되는데요?ㅋㅋㅋㅋㅋ
-
#윤리와사상 #현자의돌 #윤사 @cucuzz1123 작년부터 현돌을 접하도된...
-
ㅈ된듯.. 6
화학 틀려버림 ㅋㅋㅋ 어카지 국어.는처참해서아웃
-
6모 화작확통 백분위 80 88떴었는데 9모는 둘 다 불안정한 4컷 나왔어요 그냥...
-
딱 나형으로 나오면 황밸로 평가받을 시험지인 듯 나형 1컷 84~88이정도?
-
낮 꾸며주는 관형어로 보나요?
-
기출이랑 매이네 문학만 주구장창하다가 이제 남은 두달 동안 파이널 커리 타면서...
-
누이구루미노 데키레에스
-
9모 생2 후기 5
백호T 총평을 어제 못 봐서 못들었는데 불이었다고 그러셨나봐요..? ㄷ ㄷ 서울대...
-
기하 96(현장) 미적 92(집모, 시간x) 물론 시간 안재고 걍 푼거 미적 29만...
-
2만원 대 미친 가성비 ㄷㄷ!!! -> 29900원임
-
14시간 잡고 대략 국어 1시간 반 영어 2시간 반 생명 2시간 지구 1시간 수학 7시간
-
9모 결과입니다.
-
한국사 검정시험도 비례해서 나오진 않을거같음
-
비문학 평소에 기출 풀면 3지문에 2-3개 정도 틀리는데 이번에 비문학 4갠가? 걍...
-
과외할 수도 있는 학생이 확통이고 이번 9모 60점이라는데 혹시 지금 어떤 걸...
-
아.. 잇올 다니시는 분들 9월 더프 신청기간 끝났어요? 2
신청해야지 하다가 학교가서 수능 원서 접수하는것도 그렇고 까먹어버렸ㅅ는데 끝남..?...
-
구문이 좀 약한 거 같아요.. 김지영 쌤 즇나요 션티 이명학 다 들어봄
-
어차피 다 지네맘대로 예측이라 부정확하긴하겠지만 그래도 너무낮으면 고민이 됐었는데...
-
국어는 6모도 백분위 100 사설도 90점대라 이미 이정도면 충분하다고 생각 이럴땐...
-
지구 17번 물질 밀도는 우주 크기 세제곱에 반비례한다고 5
크로녹스가 그러네요
-
과탐 버리기 4
현역이고 이번 9모 언매 90 - 3 미적 81 - 3 영어 2 생명 40 - 3...
-
김승리T 아수라 3
내신할 때 수특 몇 지문 공부한거 빼고 연계 공부 하나도 안하고 수완도 아직 하나도...
-
이과생이 수학 5등급ㅋㅋ... 언제 수학 노베에서 탈출할 수 있을까요
-
메가컷 때문애 급속도로 우울해진 47 화붕이들은 개추 0
일단나부터
-
먼가 말이 많이나오네
-
omr엔 뭐라고 적었을까...
-
진짜 무슨 구라같음 딱 저 네개틀려서 41(2)떴어요 개념빵꾸같은데...
-
ㅋㅋㅋ
-
시간이 생각보다 많이 지났길래 뇌정지 와가지고 그냥 지구 크기가 작을땐 1보다...
-
오늘 다시 시험지 펼쳐서 보는데 마음아, 너도 이 생가에 살고 있는가 면 마음만큼은...
-
물론 까봐야 아는 거고 특히 올 수능은 어케될지 모르지만 제가 이번에 수능이...
-
큰거 오나
-
수능때 함양 이런데나오는거아님?
-
ㅈㄱㄴ 80점 중반인데 듣기 하나 날려서 아쉽
-
사문 평가원 0
평가원 문제만 뽑아놓은 교재나 문제집은 없나?
-
최저 3합7 논술 써봐도 될까요?
군대에서 코딩은 어떤 앱으로 하고 계신가요?