컴공 일기 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를 선물하세요.
-
예전에 0
나형 시험지가 이랬음?
-
사탐런 안한이유 0
개념조차도 끝낼시간이 없음.. + 홍논최저는 사1과1안된다던데 ㅋㅋㅋㅋ
-
미인정처리로 조퇴하고 싶다고 오늘 쌤한테 말씀드렸는데 1학기때 학교 선생님 추천으로...
-
투표해주세여
-
정시에서요
-
이번 9모 55분만에 다 풀고 검토까지 해서 당연히 만점일 줄 알았는데 문학...
-
1년에 스카이 3명정도 보내는 ㅈ반고… 이과 최종내신 1.37~1.4면 교과 쓸 수...
-
진짜 개졸리네 1
수2 하프1 탐2 돌렸더니 죽을 거 가틈 이걸 70일 더 해야 되네 아
-
사실 뭐 없음 근데 어거지로 짜내보자면 그래도 몇 개 있긴 함 1. 오비탈 문제...
-
과탐으로 지거국 공대가는거임 얼마나 입결이 쳐박겠음 ㅋㅋ 지역인재때문에 취업도...
-
이만 공부하러 갑니다
-
9모 동아시아사화 된거 맞음?
-
https://youtu.be/DYbt8rmJT40?si=xNfXF8fIP6XE_xR...
-
마지막 도전 3
짱이 될 거야
-
수업후 공부 패턴이나 인간관계 학업생활 어떻게하셨나여??
-
문제는 9모 직업탐구 성공적인 직업생활이에요 근로자가 만 18세이면 연소근로자가...
-
약대 복학해도 나쁘지 않을 것 같기도.. 그래두 치대 보내줭
-
이감 모고 파이널 사는거 괜찮을까요??? 조금 부담되는데
-
난도가 올라간건가? 표본이 낮은건가? 이런식이면 변별에 표점도 잘나오는거 아닌가?
-
정말 더 풀기가 싫다 N제 진자 개노잼....
-
ㅅㄱ
-
할말이 없긴하다.. 뭐 나도 영어 상평시절에 입시했으면 대학못갈거 뻔하긴해서 막...
-
사탐런 하면 쌍방손해 아님? 왜 바이럴이 있는거지 14
설명해주실 분..? 뭔가 이상한데
-
강남 갓반고 영어 잘 하는 이관데 다 외곤가요… 근데 연대에서 젤 낮은 단과대라는...
-
예전 모습의 몇 퍼센트는 보이는 것 같아서 기분이 좋네
-
틀딱구별법 0
김승리 커리 중엔 “디렉션앤 코딩” 이라는 강좌가 있었다. 이거 알면 틀임ㅇㅇ
-
찐 사탐런은 3
내년일듯 올해 애매한얘들까지 다 사탐으로 넘어갈거임
-
경제 세계사 이런 거 다 빼면 생윤 윤사 정법 사문 이런 거 오는 거임?
-
여기서 의미없이 사탐런 욕하면서 에너지 낭비하지 말고 지금이라도 오르비 끄고 책상...
-
[PDF 첨부] 9월 모의고사 주요 문항 해설 & 총평 0
Team BLANK 공통 + 미적분 교재링크:...
-
해버림 그거슨 바로 작수 언매 4틀의 트라우마를 극복하고 언매 선택. 이와 더불어...
-
물리랑 지구는 컷이 비정상적으로 높다는 글 봤는데 생1은 어떰? 여전히 꿀1임?
-
원래 6모 5등급따리 였다가 이번에 70으로 턱걸이 3등급 받았습니다. 이제 대략...
-
솔텍2 질문 2
9모 35점 나왔고 지금 솔텍1엔제랑 수완 하고있는데 솔텍2를 할지 실모벅벅할지...
-
수능이 70여일 남은 시점에서 사탐런 이슈가 오늘의 메타 이군요..ㄷㄷ 저는 오늘...
-
만점 백분위 71 기원..
-
수능의 불안정성이 커진 지금, 논술공부는 필수! 직보화논 0
안녕하세요, Uni-K LAB 입니다 메디컬 논술을 노리는, 화학1을 경험해본...
-
수시 최종 컨펌 내면서 보니까, 일반보다 컷 높은데도 많네
-
이렇게 생긴 흡혈귀한테 빨리고 싶다는데 얘 어떻게 고쳐주냐
-
사탐러들보다 공부량 최소3배는 많을텐데 …….. 사탐러들이 대학은 압도적으로...
-
왜함..? 잘 이해가 안되는 논란
-
저출산 대책에 대해서 구체적인 대안의 효과성과 국민들이 과연 납득할 수 있는지 등은...
-
영어 오답 0
다들 어떻게 하시나요?
-
작년에 한번 시험삼아봤을때, 시험삼아라 밥 안먹고봤더니 오전에 국어 수학풀때 ㄹㅇ...
-
안녕하세요. 벼락치기 수능 시작한 하수 중에 하수라고 해요. 원래 공부하던 탐구...
-
치타는 웃고잇다.
-
이투스, 잇올, 러셀 다 안되네요ㅠ 외부생은 이번 9월 더프 신청 아예 못하나요?
-
14 22 30 틀렸습니다. 엔티켓 s1 s2까지 끝내고 4규 푸는 중입니다. 4규...
-
지금이 마지막 기회임ㅋㅋ
-
ㄹㅇ 욕해봤자 달라지는건 없는데 공부하면 과탐 등급은 바뀌겠지...
군대에서 코딩은 어떤 앱으로 하고 계신가요?