컴공 일기 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를 선물하세요.
-
최근 사형 집행제 부활 이야기가 무슨 떡밥마냥 떠돌고 있는데 사형 집행하면 왜 안...
-
... 오늘 적금 100만원 나가야되는데 돈이 안들어옴
-
서대주전 연곈데 정확히 서대주랑 타남주 반대로 생각하고 풀어서 다 틀림
-
잘잘못을 따져 경우의수를 따져 에서 따져 의미가 다른건가요? 해설도 없네여
-
군수 0
3월에 공군 가서 군수 하려고 하는데 군대 가기 전까지 국어랑 수학은 잡고 가는 게...
-
지금봐도 저걸내가 현장에서 어케 풀었었나 손발에 땀이 줄줄 ㄷ
-
많은 분들이 이 라인대가 벽이라고 하셔서
-
나 이거 낙지+곱창+닭(bird)인 줄 알았는데...
-
이걸로 카페인 섭취를…
-
4000부 판매돌파 지구과학 핵심모음자료를 소개합니다. (현재 오르비전자책 1위)...
-
나머지도 1컷 이상 나오고 인설약으로 가고 싶다
-
이데아=천국=저세상=사후세계 의 존재를 증명하기위해 왜? 뒤지면 다 끝이라는 사상이 ㅈ같아서.
-
본인 짱구볼때 3
어떻게 사람이 오수를 하냐 ㅋㅋㅋ 이랬는데 내 미래로 닥칠수도 있다는 생각은 못했다 ㅎㅏ
-
33211 or 32211까지 올릴 가능세계가 있을까..?
-
Tip) 표현상의 특징 시간 절약 및 잘 안 틀리는 법 2
억지 부리지 않기 본인이 답 하나 80% 확정하고 나머지 선지 볼 때 이것도 맞지...
-
수능 보고 점수 잘 안나오면 삼수할 것 같다고 얘기했는데 너무 대학 간판 집착 하는...
-
독감 맞앗는디,,
-
그냥 아침에일어나서독서실가는게너무귀찮아요;;...학원갈돈은없고;;하
-
숙취... 0
살려줘요
-
스키마 파이널 모고 푸는데 시간이 모자라서 지문을 거의 통짜로 1개...
-
고2 수준에 맞춰서 or 고3 수준으로
-
의대를 가려했는데 올해 보니까 생각이 조금 바뀜
-
이게맞나..
-
진짜 너무너무 불안함.. 어카죠.. 순공시간을 늘려야겟죠??ㅠㅠ
-
특히 문장 관련된 문제는 상당히 빡센 듯 함 남은기간 동안 문법 전부 외워야겠네요
-
2합 6 최저 맞춰야하는데 하나는 탐구고 하나는 국영수에서 봐야하는데 국어는,,,...
-
고 1입니다. 국어 5등급, 영어 2등급 수학은 1등급인데 수학 내신은 거의...
-
검토비제발언제줌 1
진짜언제줌
-
이 시 ㅂ련이 뭘 푼거임..? 진짜 찐으로 “맞은게” 없어요 아.. ㅋㅋ 안...
-
겜하고 싶다 2
-
왜 이러고 있냐 에휴 ㅠ
-
나는! 공부가 싫다!!!! 그치만 절대로 합격해주겠어!!!!
-
슬럼프 왔을 때 0
실모치면 바로 복귀 가능
-
이감 6-1후기 2
집합들의집합들의집합들의집합들의집합들의집합들의집합들의집합들의집합들의집합들의집합들의집합들...
-
사문황님들~ 몇 가지 질문이 있습니다 1. 빈곤층이 사회적 소수자가 아닌 이유가...
-
마닳푸시거나 푸셧던 분들 한지문 풀고 오답하나여?아니면 한회차 다 풀고 한번에...
-
ㅋㅋ....
-
독서 3개 문학 3개 언매 1개 85점 자동차 브레이크 지문은 수완연계라도 너무...
-
개망함
-
반박당하면 마음이아파
-
국어는 재능인가요? 11
국어 못하는건 노력으로 올리기 힘든가요?
-
국어 Ebs연계반영 실모 뭐가 제일 퀄 좋은가요?? 7
Ebs연계공부를 초반에 하다가 국어를 놨어가지고, 지금부터 실모 하루에 1개씩...
-
이왜진?
-
한껏 저능해진 기분이다 국어 4등급의 마음을 체험하고있는 기분 진짜 개빡세게 어렵네...
-
ㅇㅇ
군대에서 코딩은 어떤 앱으로 하고 계신가요?