컴공 일기 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를 선물하세요.
-
진짜 저렇게 올림?
-
그거 분량이 어케 되나요 총 며칠치임
-
그러면 영어 버려도 되잖아
-
돈벌레 출현 0
관리비도 안 내는 게 남의 집 샤워실에 숨어 있길래 뜨거운 물로 삶아버렸읍니다..
-
수학 14,15,21,29 준킬러가 메인인 n제 추천해주세용 2
메가 패스는 없어서 메가는 빼고용
-
다들읽씹함 혼영 가나
-
모의고사에서 국어 4등급을 정도 나오는 고2 학생인데 김동욱 강민철 어느분 커리...
-
너무 사설틱하지 않은 실모 추천해주셔용 해주면 애교 해드릴께용 근데 이제 덕코...
-
이감 페이지에서 파는거랑 가격은 동일하던데 그럼 간쓸개 2권 같이 오는 건가요?
-
기준 쌩노베 의대 27학번 지망
-
개덥다 2
햇살 왜이래
-
일 났네
-
두개 난이도 비슷한가요?? 수1 수2요!
-
뭐지
-
올해 반수하면서 독재 다니게 됐는데 실모 양치기를 할 필요성은 느끼지만 막상 혼자서...
-
뭔일있었나
-
홍명보의 승부차기를 모르겠구나…
-
공부하는 날은 확실하게 공부하기 이게맞다
-
술 마셔 말어 4
추석기념 레전드 팀 모았는데
-
즐추 0
-
어느정도까지가 마지노임??? 다들 눈치안보고 질문 많이하냐?
-
맞는 말이라서 아무 말도 못하겠다
-
돼지될것같은데 2
아
-
강e분 독서 1
걍 인문 철학,과학 기술까지만 하는거 어케 생각하심? 겅제 법 사회는 솔직히 진짜...
-
안녕하세요 수학 노베이스여서 중학수학->고1수학 마친 후 강의+문풀중인데 중간...
-
오늘은 데이오프 0
지구 2개 생명 3개 풀고 컨디션 급속도로 악화.. 속이 안좋아짐
-
ㅇ
-
2등급?
-
진짜 가을 2주 미만이겠다..
-
[화학 논술] 경희 메디컬/연원의 지원자라면, 추석 벼락치기 0
안녕하세요, Uni-K LAB 입니다 메디컬 논술을 노리는, 화학1을 경험해본...
-
컨텐츠 추천좀 걍 강k를 듣기빼고 하프모처럼 풀까요
-
재수생 버전으로 현대판 리메이크 해도 재밌을듯
-
어디감?
-
ㅅㅂ
-
샤인미 많이 어려워요? 11
아직 미들인데 개어렵다길래 뒷부분이 두려워요
-
Wait for me 부를 때 울 뻔
-
전직 평가원 문제 연구원들이나 은퇴나 현직 교수들 중 희망하는 사람들 커넥트 해서...
-
핀셋 에스컬레이드 풀고나니까 혼미함 50분잡고 다 풀수가 없음
-
배아파
-
확통 6시간 컷 0
논술대비로 토일월 2시간씩 3일 수업들었는데 9평 다 풀리네요 히히
-
즐추되세요 2
-
상평시절 '길잃은 사내'로 유명했던...
-
사설 22번들은 지금 시점에서 안풀리면 안푸는게 나을까요 히카 시즌 5 푸는중인데...
-
뭔가 잘못 된 거 같은데
-
개인적으로 보자면 시대 서바, 마스퍼티스는 약간 교육청 느낌 더데유데는 평가원 느낌...
-
틀이라고 놀리지마라..
-
04면 틀이지 14
늙은이들은 수능 좀 그만 봐라 ㅋㅋ
군대에서 코딩은 어떤 앱으로 하고 계신가요?