컴공 일기 246
게시글 주소: https://i.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를 선물하세요.
-
사탐런이 판치는 지금 19
이미 과탐 선택한 고2들은 뭘 해야하오... 사문도 내가하면 많이 쉽지 않을거 같은데
-
피드백 교재보면 한문장씩 어떤 사고를 해야하는지를 자세히 명시화해놓은게...
-
시즌2 푸는데 대가리 개박살나는 거 같은디 이거 어려운거 맞다고 해줘잉 드릴...
-
어?? 뒤져볼래??
-
선물바다씀 3
-
타투 지울때 2
색깔별로 다른 파장을 쏘는구나 신기해라
-
보정컷이 만약 더프 결제해서 치는 사람말고 다른 사람도 다 같이 쳤을 땐 이정도...
-
논술에 올인해서 수능 세과목만 챙기는게 맞을까요..? 5
지금 현역인데 정시보다 논술에 더 비중을 가해서 국어랑 지구 버리고 수학(미적)...
-
아니 영어2가 ㄹㅇ 지방메디컬에서 생각보다도 치명적인데 요즘 영어 시험 어려워서 2뜰까 무섭다
-
이렇게 말하니까 ㅈㄴ이상한데 네 뭐 어쨌든 틀린 말은 아니니
-
ㅅㅂㅋㅋㅋ
-
3 4 7 다 멸망함 4는 걍 좃같아서 풀다가 포기(올해 유일)
-
다른 과목은 잘 모르겠는데 확실히 가시적으로 실력이 느는게 보이는건 수학밖에 없는...
-
일단 앱스 문학부터 빠르게 해야겠다... 앱스 독서 러닝타임이 너무 길고 강의도...
-
7개? 10개?
-
좀 인생살면서 항상 먼저 친절하게 인사하고해도 안받아주고 무시하는 사람들때문에...
-
음악사학개론 고대음악사 서양중세음악사 한국궁중음악사 의전의례음악사 미국대중음악사...
-
전 밥을 못먹어요..
-
젖지 대머리! 1
이러면 독포먹나요?
-
https://link.yeolpumta.com/P3R5cGU9Z3JvdXBJbnZp...
-
혹시 이 글 읽으실 지 모르겠는데 이매진 5호부터 8호까지 하프세트 만들어주시면...
-
T1 이긴거 나름 합리적 이유가 있었구나 이러면 젠한담이 잘하는거고 T1이 KT...
-
옯뉴비입니다~
-
KT씨발뭐냐고 3
아 ㅡㅡ
-
듄탁해 입고됐네 0
-
1빙고도 없네 2
난 뉴비!
-
빙고를 해봤는데 9
다행히 옯창은 아닌거같아요
-
17-22아님??
-
쿠팡 알바 갑니다.. 다들 남은 시간도 ㅍㅇㅌㅍㅇㅌ!
-
고등래퍼 준우승자 출신과 데뷔하게 됩니다 Listen to TAKE...
-
그냥 모든문제를 잘못보고풀고있네 뭐지?
-
문과 기준 둘다 또이또이인가요?? 거리 상관없이 간다면 다들 어디감?
-
다 재미없네염
-
와이스 황동하에 짭찬호 김도영 결장인데 오늘 지면 클난다
-
굿파트너 개 재밌네
-
님들 사문 생윤 마더텅 한권 다 돌리는데 각각 얼마나 걸림??
-
빠른 포기....
-
벌점 0
-
문학 커리 따라가려는데 문상추부터 해도 ㄱㅊ을까요? 문기정 강의 몇개만 찍먹해보니까...
-
옯창 ㅇㅈ 9
캬
-
46일차
-
대기 하나는 진짜 빨리 돌겠네ㅋㅋㅋㅋ 초반 서바 쉽게 나와도 대기는 빨리 돌았는데 ㅋㅋㅋㅋ
-
재밌어서 하루종일 물2만 하게됨
-
아니 킬캠보다 점수가 안나오네… 내가 저능아인가;;
-
ㄹㅇㅋㅋ
-
드릴 2
드릴 풀건데 1부터 차례대로 푸는게 좋을까요?
-
심지어 오개념 논란 있었던 강사도 있고 아오 머리 터진다
-
아니 나만 어려웠음 특히 첫지문
-
수2 21이랑 15중 뭐가 더 어려운가요?
군대에서 코딩은 어떤 앱으로 하고 계신가요?