컴공 일기 246
게시글 주소: https://h.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를 선물하세요.
-
하프모나 입문N제 파이널강좌 이런거 있을만한데 사실상 고2때 하는 시발점 제외하면...
-
ㅈㄱㄴ
-
이감 6-5 0
ㄱㅇㅇ쌤이 1컷 얼마라고 하셨는지 아시는분 계시나요?
-
Ebs 복습체제로 전환한다 뭔가 잘못된거 같음
-
69평보다 체감 연계율이 얼마나 될까요? 관례상 어떨지 궁금합니다. 작년에도...
-
함수가 실수 전체에서 미분 가능할 때 절댓값을 씌워서 x축과 첨점이 생겼을때 그...
-
대학가서도 못함
-
점심전에 국수영 보고 점심 먹고 수학좀 풀다가 3시쯤 탐구 하는데 밥먹고 1시부터...
-
vivi 2
오랜만에 들어도 좋군
-
담배 중독됨?
-
공부합시다 0
김민지입니다
-
언 미 영 지1. 사문 조합으로 성대의대 가능할까요 의대 증원도 됐는데..
-
파운데이션,킥오프,아이디어 이 세개 커리큘럼이 뭔지 잘 구분이 안가요,, 아이디어가...
-
아니 ㄹㅇ 땅파고 거기서 자는게 말도 안 됨... 텐트도 아니고
-
좀 높을듯..
-
어디가 틀려서 답이 안나오는지 모르겠어요,,,
-
글씨가 컨트롤이 안되는데...? 초딩때 글씨로 돌아감
-
점 ㅎㅎ
-
진지빨고 수능날이었으면 걍 포기각서 쓰고 나왔음 EBS나 유력한거 뽑아서 한 번...
-
그 쉽다던 9평도 1컷 겨우 맞고 아무리 쉬운 실모를 풀어도 100은 죽어도 안나옴
-
우기분 문학 0
아수라 듣고 있는데 거의 겹치는 지문들인가요?
-
틀리는건 항상틀림 오답해도 틀리는경우가 잦으니 오답은 필수
-
ㅋㅋㅋㅋ 미쳣네
-
원래 공부를 열심히 하는 타입은 아니고 그냥 그럭저럭… 잘하진 않지만 못하진 않는...
-
이것도 수미잡 마인드로 세뇌걸고 오답 빡시게 하고 넘겨야 하나 이젠 좆망하는거...
-
사문 생윤 둘다 2-3등급 왔다갔다하고 격일로 매일 7-10까지 생윤 사문 하는데...
-
메가대성이투스는 물리논술 인강 없는데 대 이비에스는 물리논술 해줌
-
[서론] "국어 공부는 헬스와 굉장히 유사하다."라는 게 이 글의 주장임 사실 몇...
-
어땠음 삼도극 무등비 나와서 얼탱없던데
-
꼬불꼬불 0
쓰임새랑 생김새가 나름 달라서 헷갈리진 않는듯
-
글 보면 몇분만에 조회수 세자릿수되던데 그정도로많은사람이 오르비에 상주한다고?
-
ㄹㅇ 저질 체력됐네
-
사주궁합 결혼전에 커플은 꼭 궁합 봐야하나요? 궁금합니다. 여러분들 생각은...
-
곱할때 도트말고 × 위주로 씀 그냥 습관이에여
-
정상임? 존나 어렵네 씨발
-
강k 23회 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
-
동기들이 말아주는 22수능 국어 썰 ㅈ나 웃기네 ㅋㅋ 5
동기들중에 삼수해서 온사람들한테 현장에서 22수능 국어 어땠냐고 물어보니까 다들...
-
“소아심장 분야는 아웃사이더… 과감한 투자 시급” [차 한잔 나누며] 1
김웅한 서울대병원 소아흉부외과 교수 국내 수술 가능한 곳 한 자릿수 최고 난도...
-
저의 Divine Challenge(신성한 도전)이 어떠신가여 1
다른세상의 존재를 증명하고자 시도하고 신이 다른세상에 있음을 이야기하고 신이...
-
상상뭐지 3
상상도 못한점수 ㄴㅇㄱ 엄마 나 어떡해
-
지금부터 저는 헬리콥터에요 ㅇㅈㄹ ㅋㅋㅋㅋ
-
이유는 궁금해서? 저는 일케씀
-
오늘도 내일도 통번 릴레이... 야바이... 이를 우야노... ㅡㅡ
-
생윤 사문 강의 0
내년 수능 볼건데 탐구 생윤 사문 생각중 12월에 독학기숙 들어갈거고 1월부터 탐구...
-
언매간단질문 이거 오류아닌가요..?? 덕코드림 ㅠㅜ 4
5번선지질문이요 남기다에서 기가 접사아닌가요..???
-
다른세상 논증 0
∀x(x∈A∪A^c)->∀x∃x 이식은 "모든 x가 A와 A의 여집합(A^c)의...
-
최근 사형 집행제 부활 이야기가 무슨 떡밥마냥 떠돌고 있는데 사형 집행하면 왜 안...
-
서대주전 연곈데 정확히 서대주랑 타남주 반대로 생각하고 풀어서 다 틀림
군대에서 코딩은 어떤 앱으로 하고 계신가요?