컴공 일기 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를 선물하세요.
-
롤스의 무지의 베일이라는게 정말 똑똑한 개념이 아닌가 14
이 오르비에서 매일매일 벌어지는 논쟁과 떡밥들 모두 우리가 우리의 지위와 계층,...
-
추천하고픈 문제집 있으실까요..?
-
아니 설의 간 우리 고등학교 선배 수능 접수했는데? 7
아니 이게 뭔.. 대체 무슨 생각이십니까 누님.. ㅋㅋㅋㅋㅋ
-
패로인을 볼까 러시부끄를 볼까 작화는 후자긴 한데 스토리는 전자가 나을거 같기두 하고
-
6모 이후로도 과목 바꾸는건 비추하는데, 하물며 9모 이후에 과목 바꿀까 고민하는거...
-
반영비 레전드네 걍 과탐 가산땜에그런가
-
음...
-
이번 9모에서 70점대 맞고 5등급 떴는데 기출 문제집 추천해주세요 ㅠㅠㅠㅠㅠㅠ!!...
-
45점나왔어요 조금 아리까리하게 풀긴했는데... 남은 시간동안 만점 만들수있을까요...?
-
사문 임정환 vs윤성훈 생윤 임정환 vs 김종익 짧은 근거와 함께 추천주십쇼
-
세계사 정법 12월까지 수특으로 독학 인강 26버전 업로드되면 그걸로 공부 ㅇㄸ
-
연대 기준으로 작년에 사탐 백분위 99 = 과탐 백분위 96인데 문제는 올해 상황상...
-
ㅠㅠ 16
화이팅
-
예를들어 내신 BB면 CC에 비해 설대식 몇점정도 이득이라던지
-
으악 ㅅ1ㅂ 소리부터 나오던데 걍 현기증남
-
개념은 탄탄한데 9모때 진짜 심화학습 필요한걸 느낌.. 수능69일남았는데 뭘 선택해야 후회안함??
-
사탐런과 동급 혹은 그 이상
-
맞죠? 과탐 현역 때 2등급인데 계속할까 하다가 원하는 대학에서 사과탐 유불리가...
-
가물가물해서 잘 모르겠음
-
문돌 현여기는 어쩌라고...
-
사탐런 이젠 달관중임 12
생윤은 50표본이 유입충보다 지식량 자체가 많아서 1컷이상은 큰차이없을거라고...
-
항상 물리만 잘보고 화학은 못보는 이유가 잇는거같음 물리<<다 풀면 뇌 녹음
-
9모도 그렇고 실모도 그렇고 실모풀때는 ㅈㄴ 안풀리는데 100분후에 다시보면 어떻게...
-
그냥 문제가 너무 쉬운게 맞아요 당장 물2만 봐도 20번 포물선운동은 눈풀이 가능한...
-
생윤/ 사문/ 정법/ 세지 여기중에서 두개 선택할생각인데 공부하면 안정적으로 1...
-
수능 접수 마감되면 과목 못바꾸니까
-
내가 사탐을 고평가하나 12
아무리 쉬워도 그렇지 70일만에 1이 가능하다고? 국영수도 해야될거아님?
-
그정도 수준이면 이미 사탐런을 생각안할듯요
-
어쩐지 글씨가 흐릿하고 퍼져 보이더라 .. ㅋㅋ
-
. 3
근데 갑자기 인생이 공허한 느낌 햇빛을 못 봐서 그런가 좀 걸을까 뭔가 같이 말할...
-
안됨?
-
현실적으로 본인은 어떤지 적어주셈
-
저는 파란박스친 ‘생가의 식구들’이 물고기라고 생각도 안 하고 그냥 옛날 회상을...
-
근데 그게 님은 아닐 확률이 99.8%
-
사탐런할 타이밍 이미 지났으니 괜히 깔개 영업할 꾀나 부리지 말고 (특히 그 사람)...
-
윤성훈 개념기출도표 들었고 9모에서 지문 해석을 잘 못해서 문풀량을 늘리고싶은데...
-
영어고자 특 4
낙지 메가 텔노 전부 중앙, 외대, 시립>>>>숭실대 뜸 대 대 난관대학 숭카이 wwwww
-
저는 23살 여자이고, 단 한 번도 공부라는 걸 해본 적 없었어요. 그래서 작년...
-
시발...
-
아 머리아파 1
-
1컷 47- 50 아닌가요 사탐이야 쉬우니까 그러려니 하는데 과탐이 진짜 최상위권...
-
어케 한양대 높과가 안정인데 중앙대경영이 위험뜨지 ㅋㅋ 경희대도 위험뜸
-
평가원에서 6
처음 나오는 단어가 정관사 붙어서 나온 경우도 있었나요?
-
ㄱㄱ링
-
24번 2번도 애매하긴 한데...4번 상반된 상황(ㄹ은 슬픔과 시름 없음, ㅁ은...
-
추천 좀
-
요 몇달간 잠을 너무 못자고 잠 자는 시간이 점점 더 늦어져서 스스로 잠 자는...
-
국어 23 24 0
틀렸는데 지금 보니까 오류는 없는 것 같고 그냥 내가 잘못 생각한듯.. ㅠ
-
탐구 막 바꾸지마잉
-
2^15-1 0
32767
군대에서 코딩은 어떤 앱으로 하고 계신가요?