컴공 일기 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를 선물하세요.
-
친구가 호머식 2등급이라 그러는데 맞으면 맞은거고 틀리면 틀린거 아닌가 해서요.....
-
양곰탕은 16000원 꼬리곰탕은 2만원이네
-
수능 시뮬레이션 0
유튜브에 쳐서 들으면서 하는데 한숨빌런이 진짜 만나면 최악이겠다...한지문에 한번꼴로 한숨쉬네;;
-
실모풀면 맨날 독서만 6틀 7틀해서 2등급떠요.. 한 두 문제만 더 맞추고 싶은데...
-
오리 꽥꽥 7
-
국어 순서 0
공통 + 선택 포함 고전소설 제일 힘들어해서 고전소설 맨 마지막에 풀면 거의...
-
오르비 교재 0
오르비 클래스에서 교재구매할 때 결제 확인창이 원래 안뜨나요?
-
올해 독서 0
어느정도 난이도일 거 같나요 아무도 모르는 거긴 하지만 독서 약하고 문학 잘해서...
-
어느정도 푸셨어요 다들?
-
죽을까 그냥
-
상상 5-9 0
마킹 다 하니 79분 91 독서 인문 3점틀 문학 마지막 고전시가 2점틀,...
-
차엿어 .. 여자랑 단 둘이 만나는거 부담스럽대 .. 말도 안된다 ..
-
케이비에스ㅅㅅㅅ 한국바앙소옹 (띤딘띤딘딘딘 디리링~) 뚜 뚜 삐--- 빰바밤 빠밤밤밤
-
화작 0
제가 항상 실모를 보면 화작에서 시간을 줄이려고 노력을 해봐도 빠르면17분 늦으면...
-
수능시험이라는게 3
출제자가 개념들을 엮어서 구조를 만들어내면 수험생들은 그 구조를 추론해서 맞추는건데...
-
공콘 시즌2때 가서 오르비언들 많이 보곤 했는데 이젠 추억이네
-
논술날 봐요~~~~~ 제가 안전하게 통제하겠습니다!!!
-
응애 2
아아안.아.줘.
-
사회규범의 통제력 강화를 일탈행동의 대책으로 제시하는건 머튼이랑 뒤르켐 모두...
-
동생 인강패스는 내가 끊어줘야징
-
혹시 문학/비문학 고난이도 지문 하나씩 툭 던져주고 가주실 분..! 6
그냥 여러분 기준 어려웠던 지문(문학+비문학) 아무거나 1-2개씩 툭 던져 주시고...
-
15권정도 인데 개당 만원인데 그냥 일괄로 2만원에 사가실분
-
기출 얼추돌렿느데 이감하나볼까,,,,
-
국영수한과탐임 가격15000해드림
-
다 안다고 바로 문제 들어가기보다는 배경지식을 활용한 지문과 보기 읽기 해야 틀리지 않을 거 같음
-
여기서 잡히다가 왜 사동임?? 피동아닌가…
-
슈시붙어서 필요가 없다 ㅎ
-
뚜왕뚜왕 0
뚜왕뚜왕
-
11덮 확통 0
난이도 어땟나요 33분썻고 30번 틀렷는데 평가원 기출보다 좀 어려운거같던데 맞나요…
-
미적분하면 공통 3
도움되나요?? 확통이나 기하랑 다르게 논리가 비슷해서 도움될 거 같긴 한데 어떨지...
-
기분좋은 점수로 시작하는 하루 문학이 평소보다 쉬워서 너무 좋았음 그리고 한줄평...
-
삼각함수 그래프 1
제가 풀면서 쓴 풀이인데 맞나요? 이상한점 있나요?
-
문학때문에 시간 계속 개박살나서 다 꼬이네
-
나온 거 있으면 아는사람? 요즘 사설 독서론 가끔씩 틀려서 슬프네 생각해보니...
-
춘매전 뭔가 0
느낌이온다 문실정 출제자분 말도 일리가 있다 드문 능동적 주체적 여성인물..
-
내 정신머리
-
관리를 평가할 때는 개인의 능력이 아닌 도덕성만을 고려해야 한다 왜 틀린 거예요?...
-
예열지문이랑 요약본 들고갈건데 각 교시 쉬는시간마다 볼 수 있나요? 한국사랑...
-
오르비 망했네 6
딥피드 딱 5개 뜨는 거 중에 4개가 애니프사에다 나머지 하나는 제목 상태가...
-
ㅗ 화작 2점 틀리는 사람을 뭐라고 불러요?
-
허락받는건가요?? 감독관한테
-
아 인생 8
-
1. 잠깐이라도 충분히 자며 에너지 충전하기 공부 슬럼프에 빠진 학생들은 지금까지...
-
바로 75점 떠버리네;;;
-
오느레 급씩 2
히히.. 마시게따
-
나만 어려웟나 ..
-
오바임뇨?? 걍 기출 더 보는게 낫나..
-
심찬우 나와서 노래부르고 춤 춤?
-
근처에서 혼밥 하실거임? 아님 콘섵만 보고가나
-
생글 첫강듣고 독재에서 숨죽여 울었던게 어끄제같은대 벌써 수능이 열손가락으로...
군대에서 코딩은 어떤 앱으로 하고 계신가요?