컴공 일기 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를 선물하세요.
-
성적들을 보니 1
나도 휴학하고 3반수할걸 성적 잘나오는 3수생들 보고 드는 생각임
-
특특 0
특특+실전300 역학+전자기 끝내는데 대략 얼마나 걸릴까요?? 6,9모 둘다...
-
"쌤도 다운 받으랬어요"... 족집게 학원 못간 학생들, 불법 자료방 서성인다 19
대학수학능력시험(수능) 출제 교사들은 '독점 계약'까지 맺어가며 학원에 수억 원을...
-
예상 커트라인이 비슷한 평가원 시험과 비교한 정답률 자료입니다! 낮을수록 어려운...
-
문학인강추천점여 1
메가패스만 있고.. 불륨크지않은인강 찾고 있어요
-
ㅅㅂ 좀만 쿨 돌면 사탐런 글을 얼마나 싸는 겁니까 목표가 설대나 고대인 사람도...
-
국어 #16 #23 #26 #31 #36 92인줄 알았으나 26에 5마킹한다는게...
-
자사고 내신 인설의 노려볼만한 점수라 수능최저 과탐할수밖에 없는데 이번 물리 등급컷...
-
헉ㅋㅋㅋㅋ
-
누군가의 소비(손실)는 누군가의 소득(이득)이다 라는 냉혹한 경제원리를 미리미리...
-
그 전과목 파이널 시리즈+모의고사 70일동안 풀거 사니까 거즘 160가까이드는데...
-
다른 대학들도 수업하기전에 막 강의 미리 봐야하고 그러나요? 0
그냥 대면수업만 하는게 좋은데
-
친구 6모 화생 28 29받고 화학 지구로 돌려서 하루에 2시간씩 탐구해서 9모때...
-
"텔레그램, 딥페이크 삭제 협조 안하면 韓 서비스 차단해야" 21
4일 국회에서 열린 여성가족위원회 전체회의에서 신영숙 여성가족부 차관이 의원들의...
-
열심히 했는데 6모 끝나고도 점수가 낮아서 펑펑 울었는데 아는 남자애가 너는 나처럼...
-
물리, 수학은 스킬적인 면에서 좋은거 같은데 지구도 들어볼까요 아니면 오지훈...
-
확통인데 수능 날 가능 할까요???
-
3 10 틀려서 44인데
-
김정희원 | 미국 애리조나주립대 교수 “지능 원하시면 디엠 주세요.” 최근 몇년...
-
제곧내
-
"성평등 수준 올라갈수록 출산율도 상승"… 선진국 34개국 분석 결과 13
보건사회연구원 출산율 분석 보고서 선진국에 도달하면 성평등 수준 올라가야만 출산율...
-
ㄹㅇ;;
-
초록색 파랑색이 별로 없음ㅋㅋ
-
작년 생각해보면.. 69일 진짜 죽었다 생각 이 기분 못 참
-
9모 영어가 쉬웠잔음 어제 애들이랑 얘기하는데 옆에서 A가 어제 영어 그렇게...
-
근데 재수해서 22년도에 입시성공
-
생명 3모부터 9모까지 12223 생명 3등급은 조금 에반거같은데 2등급으로 소생...
-
‘96위’ 팔레스타인과 0-0 무승부…답답한 ‘홍명보호’, 불안한 출발 1
홍명보 감독이 지휘하는 한국 축구 대표팀이 ‘약체’ 팔레스타인과 0-0 무승부를...
-
과탐에서 깔개로 대주는 퐁퐁이에서 벗어나 점수의 정상화를 이룬거임...
-
야유에 안타까운 이강인 "홍명보 감독님 100% 믿어…응원해달라" 1
▲ 이강인 "저희는 (홍명보 감독님을) 100% 따를 겁니다. 더 많은 응원...
-
바로 현강자리 들어가도 따라가는데 무리 없을까 ?
-
영어 한 등급 차이가 이렇게 크다고?영어 너무 하기 싫은데..
-
"한국 축구 사망…홍명보·정몽규 사퇴하라" 축구협 성토 4
[파이낸셜뉴스] 논란 속에 출범한 ‘홍명보호’가 첫 경기에서 약체로 평가되는...
-
과탐하자ㅏ 1
너네 없으면 망해
-
국어 기출 질문 2
평가원 지문 중에서 과학 기술 재재만 모아놓은 문제집 있나요?? 찾아도 안보여서..0
-
과탐 진도도 다 못뺀 사람 뺐는데 3등급 이상 나와본적이 없는 사람 1등급 가능성이...
-
국어(언매) 국어는 다른과목들보다 좀 낫습니다 이번에80점이고 독서1개 문학1개...
-
전 42라고 생각했는데 왤케 높지
-
[단독] 병사 화장실서 간부가 '불법촬영'…"휴대전화 확인도 안 해" 10
[앵커] 군 부대 화장실에서 남성 간부가 병사를 불법 촬영하는 일이 벌어졌습니다....
-
아차피 과탐도 별로 공부안했음…
-
화학 어땠나요? 7
저는 비킬러 준킬러 44모 n제 이것저것 다 갖다푸니까 전부다 무난하게 넘어갔는데...
-
수학 풀때 피아노 음악 같은거
-
어릴적부터 지스퍼거 출신이라 작수 쌩으로 풀고 43점 베이스임
-
국수영 다 되어 있으면 뭐..
-
사탐런 안해 4
왜냐하면 이미 원서를 냈거든요
-
제가 미대입시라 수학없어서 사탐시간이 여유가 있는데 허수 현역때 50일 남기고 생윤...
-
사탐런의 최후 19
은 없구 이쁜 내 여친 보구가셈..
-
오늘 급변경할 사람 많을 거 같은데
-
6 9모 0
국어 연계 작품 정리된 글 있을까요
군대에서 코딩은 어떤 앱으로 하고 계신가요?