컴공 일기 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를 선물하세요.
-
흠
-
오늘도 열심히 통번업무다! 오늘도 아자아자 화이팅!
-
ㄱㄱ헛
-
통으로 쉬자니 또 불안하네요.. ㅠ 어떻게 해야할까요
-
아침에 스카 청소하고 있어도 그낭 들어가서 공부하시나요?
-
눈이 잇으니 풀건풀고 나머지 몇번으로 찍을까요? 오르비에 운명을..
-
ㅇㅂㄱ 4
ㅇㅂㄱ
-
할수잇다
-
아이고오 0
힘들다아
-
이걸로 문제집들을 혼내주러 갈거에요
-
시발 겨우 군대 조금 편한 곳 가려고 이러고 잇다는게 좀 어이가 업달까...
-
team05, 06 같이 가죠ㅎㅎ
-
좋은아침이에요 13
더 자고싶어요
-
이 말이 지문을 다 읽고 문제로 들어갔을때 바로바로 기계적으로 튀어나와야...
-
중간고사가 5
내일이었구나..
-
얼리버드기상 0
-
현3등급이고 요즘 기조에 번호로 난이도 안따지는건 알지만 이때까지 기출이나 이런거...
-
얼버기이이 0
-
수학 실모 0
제가 시간이 없어서 그러는데 수학 실모 작년에 사뒀던거 남은거 풀까요 아니면...
-
수능 보러 간다는 사실 자체가 각성제라..
-
얼버기 1일차 2
-
ㄹㅈㄷㅇㅂㄱ 2
-
데뷔조이고
-
국어 실모 1
지금 이감 온라인용 파이널 12회 사서 주2회 풀고잇는데 상상 온라인용 10회...
-
지금도 시험기간인데 시험 전날은 항상 불안해서 잠을 못자겠음... 수면제라도 먹어야하나
-
테라플루 미쳣네 0
이틀만에 감기 증상 거의 사라짐 ㄷㄷ
-
왜냐면... 그냥 제가 안좋아함! ㅈㅅ
-
이게 권태기인가 아니면 그냥 불만이 쌓인건가 온갖 부정적인 생각으로 휘감겨있네 막...
-
평균적으로 국어 3-4 수학 만년3 영어2임 과탐은9모 생명 한문제차로3 지구3...
-
오늘은 자고 내일 용서를 구하자
-
어제 알람 맞추고 평소 자는 시간보다 2시간 일찍 깨려고 하니까 자다가 깨긴 깼는데...
-
시그모 9회 0
이거 왤케 어려움?? 풀어보신분들 솔직후기 가능하신가유.. 저는 어려웠어가지구 ,,
-
단절vs예방 0
존재 부재 ㅡ.ㅡ
-
고2고 수능날 모의수능 보러 갈 건데 수1은 어느 정도 완성하는 단계이고 수2는...
-
삶의이유가뭘까 2
아무란열망이없다 난왜살지
-
기출 마무리 프로젝트 하시나요?(추가로 제가 문학을 30분가까이 시간을 씁니다...
-
38일의 기적 1
못할것도 없다뇨이 96 100 75 44 39 ->98 100 1 50 50
-
예1 없애는건가 그거 아니면 가능한가?.? 일부 학교는 예2때 해부학 이런거 하던데
-
동아리 머야시발 10
유은희가 정실인건가 강수연은 뭐가되는거지
-
지1 오지훈 매개완 돌리고 마더텅으로 기출 2회독 돌렸습니다. 실모는 더프가 다인데...
-
40일의 기적 5
그딴거 없는거 알긴하는데 독재 끝나고 스카가서 더 하다가도 결과가 안좋으면 다...
-
까뮈는 삶 그 자체에는 아무 의미도 없다고 했지만... 다른 사람들의 여러 생각과...
-
님들 2023 물리 교재 써도됨? 어차피 물리는 신유형이 0
업ㅎ지않나 일당백 하나 워크북 풀까고민눛
-
ㅜㅜ
-
무물 16
이 시간에도 사람이 있나
-
강대 x 1
수강기간이 며칠인가요??
-
안녕하세요. 영화 인터스텔라보고 너무 재밌어서 찾아보다가 2016년...
군대에서 코딩은 어떤 앱으로 하고 계신가요?