컴공 일기 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를 선물하세요.
-
취침! 9
안녕히주무세요!
-
후...
-
생명과학 책 한권 샀는데 300문제 중에 오류가 20문제가 넘어서 풀다가 풀다가...
-
어떤 자연수에 대하여 홀수면 3을 곱하고 9를 더한다 짝수면 2로 나눈다 이 규칙을...
-
집으로 우편 날라오나요?? 합격증
-
좋은 퀄리티를 0
합리적 비용에 제공한다면 서로 윈윈이다.
-
고2정시..입니다.. 찐 막. . . 의견도 남겨주시면 정말 감사하겠습니다 .....
-
좋은 방법인거 같아서 따라하기로 했습니다 낄낄
-
7+9 2x3+6 히히
-
에쎄 수 딱 대셈
-
어디서 만들어요? 궁금
-
방학조아 5
흐흐
-
마무리까지화이팅!!!!
-
바나나는 규모의 경제가 극단적으로 발달해 원가로만 따지면 껌값도 안된다 ???:...
-
굳이 비싼 돈 내고 검증된 가게에서 시키는 보람이 있다 +오늘 저녁으로 육계장 추천 받아서 다행이다
-
지나가는 수험생 1인입니다. 개인적으로 문제를 만들어서 배포하는 것에는 책임감이...
-
흐엥 0
후엥
-
이제 킬캠으로 들어간다@
-
성장해서 기분 좋다
-
속세를 멀리할 때가 왔다
-
와이지 속절없이 추락하자…결국 '블랙핑크' 나선다 [종목+] 1
‘블랙핑크’가 내년에 ‘완전체’로 월드투어에 나선다. 블랙핑크의 ‘조상’ 격으로...
-
하반기 전공의 모집, 지원 적을듯…교수들 '제자 안받아' 보이콧(종합3보) 1
복지부 수평위, 하반기 전공의 '7천645명' 확정…수련병원 신청보다 62명 줄어...
-
맛난 거 시켜서 먹기 직전인 내가 승자인듯
-
내가 푼(?) 5모 학평 재업할까 그거 22점 나왔는데..
-
내 인생 최고의 피자 25
잭슨피자의 스테디셀러 ”슈퍼잭슨“ 반드시 드셔보셔야 합니다..
-
오늘 하루는 알찼다 14
무려 밖을 두번이나 나갔어요
-
왐마 교육청 7모 문항 수열 하나 올린거 제가 떡빱 뿌린건줄 와.... 놀래라.....
-
한완수 0
시발점 수1수2 다끝내고 한완수 실전개념 하고 미적분은 교과개념부터 실전까지 다...
-
“누가 책임 질건데” ㅋㅋㅋㅋㅋ Ai백날 개발해봐야 탑에는 책임자가,,,,
-
1. 일단 조건부터 조잡하고 볼륨이 많아서, 발상보다는 이것저것 조건을 조합하는...
-
“지인선n제”
-
수능결과가 어떻든 몇번 더 수능 봐보고 싶어서 군수하려는데 그냥 지금 바로 군대...
-
검증만 하죠왜? 11
방패증 총증은 어디 엌ㅋㅋㅋㅋ
-
학습용으로 푸는 사람 있나
-
저나이에 홈런을 치네 이토이 81년생이던데
-
누가누가 잘찍나 26
다음은 동료 교사와 보건 교사의 대화 내용의 일부이다. ㉠과 ㉡에 들어갈 단어를...
-
메인글에 저격글까지 올라왔는데도 글 여러개씩 써대며 댓글까지 쭉 달아야할 상황임?...
-
싸게 배웠다 생각해요 무료 배포도 아니고 돈 받고 쳐 파는 책 오류 존나 낸 사람...
-
통장잔고 왜이래 0
ㅠㅡㅠ
-
순정만화땡기네 ㅇㅇ...
-
메타 난 참여 힘드네 24
닉값 세게해서.. 아니 풀 수 있어야 뭘 코멘트를 하든가 말든가 하지
-
뇌가 고장났어 3
꼴랑 9시간하고 집중력 박살이라니
-
조용히 관전하는
-
내 돈,,,,ㅠ
-
끄적끄적계산은귀찮아서안해요 맞기는하려나몰루
-
따흐흑 사고싶다
-
모이고사자작문항 8
새들에게모이를주지마시오
-
그냥 맘에 안들면 안풀어보고 욕도 안하면 안되는건가? 세상은 왜이리 매정한걸까 난 이런세상이 싫어
군대에서 코딩은 어떤 앱으로 하고 계신가요?