컴공 일기 246
게시글 주소: https://app.orbi.kr/00068783679
… 예… 오랜만에 들어와서 요새 풀고 있는 알고리즘 코드 하나 올려놓고 갑니다…
여전히 꽤…는 아니어도 열심히는 사는 중입니다…
간단한 해설을 하자면 소수를 찾는 알고리즘입니다.
주로 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평텔그 고연대 낮과 라인인 본인을 고경제 적정합격 라인으로 만들어줄 정도이다...
-
9모 뽑을라면 0
어디서 뽑는게 젛디
-
9평 85점 평소에 독서는 그냥 기출 돌림 화작은 양치기 하고 문학은 ebs만...
-
미적 n제 0
미적 N티켓했고 드릴 마지막으로 풀건데 그 전에 할 미적n제 추천해주세요
-
고대를 버렸어야 했다.....
-
수능때 2
백분위 98 100 2 97 96이면 지거국의 ㄱㄴ?
-
새기분 완강했고 6모는 언매 96점 받았는데 지금 시기에 뭘 하는게 맞을까요? 제가...
-
물1 69평 1컷 48 50 물2 69평 1컷 50 50 이 정도면 표본 수준...
-
9모도 끝났잖어
-
6모 2등급에 원래 수학을 못하긴 하지만 최근 더프나 사설 치면 평균 80점은...
-
사탐런 1주만에 받음 점수임. 생명 점수랑 비교해봐
-
9평 블랭크 나면 그럴수도 있다고 보는데 6월하고 9월 채점결과 보면 지금까지는...
-
21번 수학 10
곡선과 직선 사이에 함수가 존재하려면 무조건 만나는점이 있다 이런식으로 풀어야했나?
-
그동안 잘 버텼음 연고라인 이상 국수성적을 가진 분들은 6교시 원서영역 과탐필수...
-
돌고래 미안 3
너 게시글 쭉 봤는데 내가 5월에 사문으로 사탐런하게 해준 사람이 너였더라 덕분에...
-
물리 실모 0
다른 강사 실모풀다가 듣던 강사랑 풀이 다른 경우 많나요 만약 다르면 어떻게 받아드리시나요
-
공부합시다. 0
윤석열입니다.
-
몬가 허해
-
적분퍼즐 극복 1
극복 강의나 n제 추천 점 해주세요
-
'5조원 투입' 제주 2공항 사업 9년 만에 본격화…여전히 산 넘어 산 2
[앵커] 찬반 논란을 빚은 제주 2공항 사업이 결국 본격화했습니다. 5조원 넘는...
-
글 제목에 사탐,과탐만 있으면 기가막히게 찾아다니긴하던데 ㅋㅋㅋ 오르비 24시간 상주하는줄
-
[속보] 검찰, 여신도 성폭행 JMS 정명석 항소심서 징역 30년 구형 1
▲ JMS 정명석(왼쪽) 검찰, 여신도 성폭행 JMS 정명석 항소심서 징역 30년...
-
생각해보니까 나는 지구5 나오는 ㅂㅅ인데 돌고래 보고 사탐런 바이럴 ㄷㄷ하면서...
-
으으
-
준비 갈 완료 0
치타는 수능 원서 접수하고 스카오는길임니다 혹여나 안 하신 분들 오늘까지니...
-
오르비측에서『독해분석』을 docs로도 출간하도록 허용해 주신다고 하네요. 다음주에...
-
생1도 많이 어려웟나요?
-
어떻게 봐야 되는지 모르겠네요.
-
3점 1개라도 틀리면 3뜬다는 물리 오답률 1,2,3등이 3점짜리인데 1컷...
-
의대합격후,졸업,그리고 또 10년 정도 일하면... 5
연봉2억 잡고 10년 일하면 20억 모아서 네 옆집으로 이사가야겠다 근데...
-
사문실모 추천 3
사문 실모 시대인재가 좋다는 얘기를 들어서 사려고 하는데 멀 사야되나여.. 그리고...
-
최저 충족 가능 최저 빡세고 면접 잇어서 선배들 잘 갔는데 올해 면접...
-
김과외 앱으로 영어 과외 구하려는데 과외 구하는게 첨이라 어렵네
-
이주호가 6개월 버티면 이긴다는 생각은 어짜피 인서울 빼고 니들 다 다시 시험봐서...
-
이 문젠데 보기에서 '자신을 물고기에 투영'이라길래 어떤 물고기에 화자가 자신을...
-
9모 83점 2등급 나온 사람인데요.. 항상 75-77사이 3등급 뜨다가 이번에...
-
9모때 15번까지는 다 깔끔하게 맞았는데 그러고나면 시간이 얼마 안남아서 남은...
-
최상위권만 손해지 대부분 기회의장 아님?
-
제 풀이 문제점이 먼가요?
-
사람이 꼭 누군가를 좋아해야만 살아가는 것은 아니잖아 0
누군가를 좋아하는 마음이 없어도 살 수 있어 사랑받지 않아도 살 수 있는 것처럼...
-
수능 접수 완 2
화작미적지1물2
-
사문 지구 커리 1
사문 44(1,2,16번 틀) 지구 44 (16,19 틀) 지구는 크로녹스랑...
-
저만 반수할래요
-
진짜 궁금해서 묻는데 사탐 1-2달 만에 1가능이면 8
나머지 96%는 뭐하는 사람들이에요?
-
22때부터 수학은 불이 없었는데 올해는 불일듯...ㅋㅋ
-
고2 9월 29번 분석입니다.
군대에서 코딩은 어떤 앱으로 하고 계신가요?