컴공 일기 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를 선물하세요.
-
영어공부+솩공부
-
실시간 열받아서 2
케로로 초코칩 쿠키 먹을꺼야
-
수능이 다가온다는 의미겠지 수능날 개같이 지워야지
-
맞팔ㄱㄱㄱㄱ 4
ㄱㄱㄱㄱ
-
내 텅장 4
올해초엔 분명.... 갑자기 현타오네 재수비용 ㅆㅂ이...
-
은테복귀 15
얼마만이지
-
ㅎㅎ..
-
수학 파이널 토탈리콜 + 원솔멀텍파이널 ㅁㅌㅊ?
-
13틀 진지하게 못풀었음 뭔가 예상되는 방향에서 계산이 안됨 다른 길이 안 보여서...
-
진짜 어렵네요.. 글을 앞으로쓰는건지 뒤로쓰는건지 뭐라고 쓸지는 알겠는데 무슨...
-
뭔 미필새끼들이 군기타령 ㅋㅋ 군대에서 마저 군기타령안하는데
-
수능 공부
-
에너지드링크 ON
-
스카 6층인건 2
담배를피지말라는건가...흠
-
10만원짜리 패드로 인강 듣고 있는데 나중에 피뎁 쓸 일이 많아 보여서,,
-
급함
-
갈아만든 ldH 1
-
글 올라오는 속도 왤케 느려
-
다시 영어 기출 분석해보니깐 ㄹㅇ 다른 어떤 지문보다도 재미있네요 보는 시야가...
-
완전 새책입니당 가격은 8천원 입니다 교대역이나 대치동(은마사거리) 직거래 돼요
-
ㅈㄱㄴ
-
좀 대충 어림짐작을 해보고 싶은데 아직도 많아봐야 한 10퍼도 안들어온듯...
-
59일만 하면 되는데 100일때부터 달리지도 못했는데 나쁘지 않은 환경인데 후..
-
6모3 9모3 나왔습니다. 계속 정체된느낌이 들고 해서 실모를 돌려볼까도 생각중인데...
-
9평 느낌 반영 독서 자작 투척 [측정과 국제표준] 1
반영인가? 사실 몰7루?
-
미적 높2 인데. 브릿지랑 비교하면 난이도 어떤 편인지도 말해주세요
-
3항부터 53항까지의 홀수항의 갯수,3의배수항의 갯수 이런거 구하기 나만 ㅈㄴ못함?...
-
풀렸나요? 시대 시대 시데 시데 ㄱㅇㅇ ㄱㅇㅇㄱㅇㅇ
-
아니 가격이 이게 맞냐 16
하... 안 되겠다
-
자꾸 금지어 있다고 떠서 개빡치는데 뭔지 안 알려줌
-
메인글 개짜증 4
하남자식운영 걍말할것이지 괜히 찝찝하게
-
예비고3이고 고3기준 84 88 92 요정도인거같아요(실모풀면 대부분 88이에요...
-
7월쯤에 이훈식쌤 커리를 타기시작해서 이제야 개념, 기출문제를 끝냈는데 지금시점에서...
-
아니 전자레인지를 왜 못 쓰게해 화나게 ㅎㅎ
-
사설에서 가끔 틀릴 때 있는데 이제까지 평가원에서 발음 안 준적 있나
-
왜냐하면, 미래의 경영자는 극소수이기때문입니다
-
확통 80이면 평가원 몇등급임?
-
최대 나이많으신분은 몇살입니까..!?
-
지금은 뭐 사설에 수두룩빽빽하니까 1분 컷인데 당시에는 좀 충격적이었나요? 급수...
-
저는 10월 말쯤에 나갈 것 같은데 다들 수능 전날까지 다니심?
-
솔직히 영어는 2
60분으로 줄여도 된다고 생각해요..
-
내용 캡쳐해서 보여줫더니 그 내용 네이버에 검색해서 내 블로그 찾아냄,,,,,,, 소름돋아
-
본인은 하나도 못받고 지능이 다 동생한테 몰빵됨... 내가 받은건 유일하게...
-
시내 나갔다오기 왜이렇게 힘드냐..ㅋㅌㅋ
-
도형 마냥쉽진않던데
-
수1 자체가 실전개넘이랄게 없는건가?
-
선생님들이 허락해주셔서 그런가? 궁금
-
ㅈ댓네 이거 언제 다 풂
-
가기싫어서 스카에서 뻐기고있는데..
-
버릴거버리고 다맞추는사람 도대체 그게어떻게되는거임
군대에서 코딩은 어떤 앱으로 하고 계신가요?