컴공 일기 246
게시글 주소: https://snu.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를 선물하세요.
-
수능 보러 간다는 사실 자체가 각성제라..
-
얼버기 1일차 0
-
ㄹㅈㄷㅇㅂㄱ 2
-
데뷔조이고
-
국어 실모 0
지금 이감 온라인용 파이널 12회 사서 주2회 풀고잇는데 상상 온라인용 10회...
-
지금도 시험기간인데 시험 전날은 항상 불안해서 잠을 못자겠음... 수면제라도 먹어야하나
-
테라플루 미쳣네 0
이틀만에 감기 증상 거의 사라짐 ㄷㄷ
-
왜냐면... 그냥 제가 안좋아함! ㅈㅅ
-
이게 권태기인가 아니면 그냥 불만이 쌓인건가 온갖 부정적인 생각으로 휘감겨있네 막...
-
평균적으로 국어 3-4 수학 만년3 영어2임 과탐은9모 생명 한문제차로3 지구3...
-
오늘은 자고 내일 용서를 구하자
-
어제 알람 맞추고 평소 자는 시간보다 2시간 일찍 깨려고 하니까 자다가 깨긴 깼는데...
-
시그모 9회 0
이거 왤케 어려움?? 풀어보신분들 솔직후기 가능하신가유.. 저는 어려웠어가지구 ,,
-
단절vs예방 0
존재 부재 ㅡ.ㅡ
-
고2고 수능날 모의수능 보러 갈 건데 수1은 어느 정도 완성하는 단계이고 수2는...
-
삶의이유가뭘까 1
아무란열망이없다 난왜살지
-
기출 마무리 프로젝트 하시나요?(추가로 제가 문학을 30분가까이 시간을 씁니다...
-
38일의 기적 1
못할것도 없다뇨이 96 100 75 44 39 ->98 100 1 50 50
-
예1 없애는건가 그거 아니면 가능한가?.? 일부 학교는 예2때 해부학 이런거 하던데
-
동아리 머야시발 10
유은희가 정실인건가 강수연은 뭐가되는거지
-
지1 오지훈 매개완 돌리고 마더텅으로 기출 2회독 돌렸습니다. 실모는 더프가 다인데...
-
40일의 기적 3
그딴거 없는거 알긴하는데 독재 끝나고 스카가서 더 하다가도 결과가 안좋으면 다...
-
까뮈는 삶 그 자체에는 아무 의미도 없다고 했지만... 다른 사람들의 여러 생각과...
-
님들 2023 물리 교재 써도됨? 어차피 물리는 신유형이 0
업ㅎ지않나 일당백 하나 워크북 풀까고민눛
-
ㅜㅜ
-
무물 16
이 시간에도 사람이 있나
-
강대 x 1
수강기간이 며칠인가요??
-
안녕하세요. 영화 인터스텔라보고 너무 재밌어서 찾아보다가 2016년...
-
역시 당대표 짬밥 어디안가는듯
-
하다못해 어제 오전에라도 시작했다면..
-
생각만해도 아찔하다
-
오래된 생각이다
-
메모리 개 많이 잡아먹어서 안쓴다는데
-
재수 보고 있는데 사탐확통 공대가 올해는 괜찮은거 같던데 내년도 비슷할까요?...
-
공 문제 말고 다른문제는 쉽지않음?
-
현무 0
현무5
-
2025 메타독서 천재 2025 하우에버X타임해커 [2025] 메타독서 천재 01강...
-
수능 수학 11
예상하는 난이도는 얼마인가요? 딱 올해 6모 난이도만큼 나왔으면 좋겠는데 그러면...
-
혀 뿐만 아니라 장도 포함
-
자퇴예정인 07입니다 생명 개념 1회독 거의 다 돌려가고 있습니다 박선우 선생님...
-
목말라서 일어남 2
잠 깼다
-
제가 지방사는 현재 고1인데 제가 공부를 너무 안해서. 내신도 어중간하게 3점...
-
취업하기싫노 2
에휴핑
-
연논 3
다들 무슨과씀? 나는 기계공학부 씀 65000일단 날린거같고 회나 사먹을걸그랬나 쩝
-
확인~ 자러감
-
시즌1 항상 1등급 나와서 좋아했는데 시즌2에서 개뚜까 맞네요 ㅋㅋㅋ ㅜㅜ 시즌3은 어떨지
-
현돌개념 간간히 보고 검더텅 1번 풀고 아무것도 안했어요… 개념을 다 까먹은느낌이라...
-
더 커지고 싶다
군대에서 코딩은 어떤 앱으로 하고 계신가요?