컴공 일기 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를 선물하세요.
-
수능이 70여일 남은 시점에서 사탐런 이슈가 오늘의 메타 이군요..ㄷㄷ 저는 오늘...
-
만점 백분위 71 기원..
-
수능의 불안정성이 커진 지금, 논술공부는 필수! 직보화논 0
안녕하세요, Uni-K LAB 입니다 메디컬 논술을 노리는, 화학1을 경험해본...
-
수시 최종 컨펌 내면서 보니까, 일반보다 컷 높은데도 많네
-
이렇게 생긴 흡혈귀한테 빨리고 싶다는데 얘 어떻게 고쳐주냐
-
사탐러들보다 공부량 최소3배는 많을텐데 …….. 사탐러들이 대학은 압도적으로...
-
왜함..? 잘 이해가 안되는 논란
-
저출산 대책에 대해서 구체적인 대안의 효과성과 국민들이 과연 납득할 수 있는지 등은...
-
영어 오답 0
다들 어떻게 하시나요?
-
작년에 한번 시험삼아봤을때, 시험삼아라 밥 안먹고봤더니 오전에 국어 수학풀때 ㄹㅇ...
-
안녕하세요. 벼락치기 수능 시작한 하수 중에 하수라고 해요. 원래 공부하던 탐구...
-
치타는 웃고잇다.
-
이투스, 잇올, 러셀 다 안되네요ㅠ 외부생은 이번 9월 더프 신청 아예 못하나요?
-
14 22 30 틀렸습니다. 엔티켓 s1 s2까지 끝내고 4규 푸는 중입니다. 4규...
-
지금이 마지막 기회임ㅋㅋ
-
ㄹㅇ 욕해봤자 달라지는건 없는데 공부하면 과탐 등급은 바뀌겠지...
-
정부 정책이 완벽할 수가 없기 때문에 꿀빠는 쪽은 무조건 생김. 당장 생각나는 것만...
-
정시러 논술 3
6장 다 채워야하나... 경한 인문 고대 경영 성대 글경영 더 쓸 곳이 안 보임 으으음
-
연애하면 수능보기 싫어짐..
-
개같이 개같이 강등방어 성공 ㅋㅋ
-
헉..
-
내년에 하실생각이 없으시면 국수생각해서 잘 선택하세요….
-
접수증 내놔!!
-
지구언제망함 0
-
선택에 후회하지 않았는지 생각해보시고 수능일까지 화이팅 합시다!
-
상상vs바탕 0
상상은 파이널10회차+연계문제집100지문? 두개해서 16만원이고 바탕은...
-
너 못생겼잖아 ㅋㅋ 너한테 흑심이 생기는 게 가능하겠냐고~
-
ㅇㅇ?
-
우리 역스퍼거들은 새로운 세상을 알고싶은 자네들을 매우 환영합니다 1등급이 많아져도...
-
언미생지고 9모 원점수 95 92 2등급 45 42인데 연대 가능이라고 떠서요.....
-
경제런 많이 보이던데 15
경제 1표본은 절대 런치는얘들 생각처럼 계산못하는 빡통허수문돌이가 아님.. 맘대로...
-
언매 미적 영어 생1 지1 6평 원점수 88 81 81 47 42 백분위 98 96...
-
보통 자칭 남사친들<<< 100퍼 흑심있음 아주가끔 있을 수 있는데 그건 둘중...
-
인강 0
사탐을 이투스꺼를 듣고잇어서 단일비만 듣긴 햇는데 지금이라도 김승리들을까 고민되요...
-
왜 아래에서 계속 싸워요
-
화작미적사탐(쌍사)고 원점수 98 67 92 47 45 백분위 96 71 1(절평)...
-
오늘 지출 7
증사 마넌 버스비 삼처넌 원서비 사만이처넌 계:오만오처넌 아.
-
사탐해도 제한 없었으면 제가 했을 조합
-
런도 런 나름이지 이상한 곳으로 도주하시면 안됩니다 9
예를 들어 경제나 세계사로 도주를 하시게 되면 끔찍한 사태가 발생할 수도 있습니다..
-
여친 고딩동창이 여친한테 연애중인거 아는데도 불구하고 둘이서 영화보자고 플러팅해서...
-
난 경고했다
-
https://www.youtube.com/watch?v=ZRebVq_TseY
-
이 중 적지 않은 수가 본인들은 콩고 가서 사탐원주민 학살하는 레오폴드 2세가...
-
어어 화내지 말고 긁히지 말고 나도 화1하는데 솔직히 사탐 개노잼이고 화1...
-
어디가 젤좋음,,,?
-
4고 시즌1 수1 푸는 중입니다. 1권에 3일씩 총 10일정도 잡아두고 수1 수2...
-
내가 봤을 때는 사탐런 자체로 욕먹는 거라기 보다는 글의 태도에서 의도가 보여서임....
-
사장님이 박스살짝 열어보고 원하는거 주셧음...
-
1. 굉장히 착하고 귀욤귀욤하거나 2. 어딘가 나사가 한 열개쯤 빠져있거나 둘 중 하나 같다
-
윤하 '사건의 지평선', 고등 교과서에 실린다…문학 지문 수록 7
가수 윤하의 히트곡 '사건의 지평선'이 고등 교과서에 실린다. 6일 소속사...
군대에서 코딩은 어떤 앱으로 하고 계신가요?