컴공 일기 246
게시글 주소: https://ys.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를 선물하세요.
-
겸손한 연대 3
노벨문학상으로 연서고 만들었다가 알아서 서연고로 다시 돌아감 겸손…하다고 해야할까?
-
백지정리 자체체작 할 생각인데 29일 남기고 해도 ㄱㅊ?
-
디카프 시즌1 4회까지 풀었는데 차례대로 42 36 33 42 이렇게 나옵니다...
-
시킬게 안떠오르네
-
( 인턴 실습 파행, 국립대 출신 병원인턴 달랑 3명 : 의대 교육시스템 마비 ) 1
https://news.kbs.co.kr/news/pc/view/view.do?ncd=8081687
-
연대 재시보나요 0
물론 저는 상관없지만 대학이라는 학생들의 인생의 큰 영향을 미치는 시험이 이렇게...
-
문프의 금속 4
Moon's Metal ㄷㄷㄷㄷ
-
ㄷㄷㄷ
-
이건 고로시 아님?
-
좋아요 받으면 들어오는 거였구만 왜 칼럼쓰는 분들이 덕코부자인지 알아냈다!
-
얘네는 수습할게 많은 애들이라서 가장 마지막에 철수하는 편 글구 사실 얘네가 철수할...
-
막상 다시풀어보니까 왜이렇게 못풀었나 싶네 초면에 되게 어렵고 시험끝나면 별거아닌게...
-
어캄? 영어 듣기평가하고 있는데 갑자기 웨에에에에애앵 소리가 나더니 북한이...
-
ㅎㅇ 9
-
와 대박... 2
이걸 개입해주시네
-
저 지금 남부지방 쪽인데도 으슬으슬함
-
아 ㅋㅋ
-
역시 0
대 석 열
-
연대 재시보겠네 2
석열석열아 ㅋㅋ
-
[속보]尹, 연대 논술 유출에 "책임자 철저 문책..엄정조치하라" 17
[파이낸셜뉴스] 윤석열 대통령은 2025학년도 연세대 수시모집 논술시험 문제유출...
-
軍 "북한 경의·동해선 도로 폭파에 대응사격 실시" 1
북한이 남북 연결 도로 요새화 발표 엿새 만에 경의선과 동해선 도로 북측 지역에서...
-
5~6시간 하면 넉다운됨 흑흑
-
수2 같은 경우는 대가리 박고 1 2시간 고민하면 풀리는데 수1은 수2의 그 1 2...
-
이런식으로 다시 나오면 또 틀릴듯 오답 근거가 관련성이 없어서라는데 막상 문제풀때는...
-
저것들이 슬슬 보복쳐맞은지 오래되서 정줄이 나갔구만 미루나무 시비털다가 나라...
-
[속보] 尹, 연대 논술 유출에 "책임자 철저 문책..엄정조치하라" 6
https://naver.me/5RhYxLFB
-
이제 수능 30일 남겨둔 시점에서 화학1 공부법, 시간 단축 등 질문이 많이...
-
과외준비하다 수능 30일 남은거 보고 뭔가 짠하고 남일같지않아서 오랜만에 로그인함...
-
오랜만에 풀어봤는데 10모 20번 정답 9/4 맞나.. 10
심심해서 문제 받아서 하나 풀어봤는데.. 보기가 안나와있어서 혹시 수험생행님들...
-
실모에서 계속 3-4등급인데 수능에서 2-1 나오는게 가능함?
-
당근 문과입니당 진짜 몰라서 여쭤보는 거예요 혹시 먼가 제 질문에 문제가 잇다면...
-
놀러다닐때가 수학 2등급이었는데 왜 이젠 2등급을 받지도 못하는거임 뭔가 잘못된거...
-
고1 2학기 기말 끝나고 멘토링 초청 강의로 오셨었음 고려대 의예과?셨던 것 같은데...
-
당근 문과입니당 진짜 몰라서 여쭤보는 거예요 혹시 먼가 제 질문에 문제가 잇다면...
-
갑자기 실모 치니까 예상 등급컷 3~4씩 나와댐 ㅅㅂ 9덮까지는 생명 괜찮은줄...
-
글 대충 보니까 작년의 재림 같긴 한데 그래도..
-
이게 작년 수능 난이도?
-
빡갤럼 씨발련이 12
10모 30번이라길래 ㅈㄴ열심히 풀면서 와 이거 현역 절대 못풀겠다 이러고 있었는데...
-
(이제끝남) 오늘 공부 가능?
-
(선착순마감)41기 대면멘토링 서강대학교 편 신청하기!! 0
41기 대면멘토링 서강대학교 편안녕하세요, 여러분의 꿈의 열쇠를 찾고 조여주는...
-
허허..
-
1,2평이 별론데 어떰??
-
그냥 지원자 전부 합격시키고 향후 5년간 모집 안하는게 어떰?
-
작년도 그러도니 왜 수능 어정쩡 한달 남은 시기만 되면 힘이 쭈욱 빠지냐...
-
일반인 수준에서 철학자 수준질문을 던지면 완전히 반박 못하긴해서
-
캬캬캬캬캬
-
레전드 기상 0
오늘은 게임이나 해야지
-
화학반응식에서 고체 있는데 기체 부피 구할 때 같이 더해버림 ㅋㅋㅋ
-
가장 열심히해야할 시기에 두려움 기대감 게으름 나태함 온갖 감정이 다 튀어나오노
-
대회시즌 끝 1
올해는 부상이슈로 큰 기대는 안했는데 다행... 이제 수능 30일의 전사 달려야지
군대에서 코딩은 어떤 앱으로 하고 계신가요?