컴공 일기 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를 선물하세요.
-
국어 23 24 2
틀렸는데 지금 보니까 오류는 없는 것 같고 그냥 내가 잘못 생각한듯.. ㅠ
-
탐구 막 바꾸지마잉
-
2^15-1 0
32767
-
다들 뭐 국영수 안정 1떠서 그런말 하는거지? 걍 컷에 쫄지말고 지금부터는 하던거에...
-
내년에 2
언기한경 렛츠고ㅋㅋ
-
텔그돌려보는데 0
동기부여 잘된다 진짜 수능때까지 열심히 달려야지
-
46인데 진짜 불안해 뒤지겠음…
-
하는 사람들은 어차피 바꾸나 안바꾸나 탐구는 좆박은거 같으니 히고싶은대로 하쇼
-
과탐 사수 그것이 낭만 n수니까...
-
계산이 너무행
-
사탐런만 아니었어도
-
김윤환T 조윤병천T 연대파이널 들으려는데 누가 나을까요? 수강후기랑 추천좀여...
-
본인 7월에 정법사문 시작했는데 사문은 낭낭하게 1 떳지만 정법은 개말아먹고 3뜸...
-
확통 2컷으로 0
서성한 가려면 국어 2등급 사탐 1등급맞아야하나?
-
알아버렸다 "합격"하는 방법을...
-
지금까지 열심히 후기 쓰고 성적표 ㅇㅈ해도 딱 한번밖에 못 갔는데 도대체 오르비가...
-
문학에서만 2개나갔는데..
-
고2 남학생 윈터 기숙 양지&서초&강대&용인 등 질문 1
양지 메가 서초 메가 용인 남자관 강대 이정도 알고 있는데 어디가 좋을까요? 성적은...
-
마지막 인가…
-
어차피 책임은 본인이 지는거니까 진정 사탐이 꿀이라고 생각하고 지금부터해도 연초부터...
-
98+72를 160으로 적었는데 다시봐도 160으로 봐서 왜 틀린지 몰랐던..
-
공통 다 풀고 40분가차히 남았는데 28 29 30 하나도 못 품 ㅋㅋㅋㅋ
-
평백 몇정도 받아야 합격할거라 생각하시나요?
-
9모 0
하루 공부시간 2시간. 왜 시작했는지 모르겠다. 근데 6모보다 성적이 올랐다....
-
지학이 변별요소가 이제 계산메타인거임? 뭔가 개념의 심화보다는 찐 계산메타같은데
-
수시 재수하는데 적정에 딱 걸쳤는데 이거 합격한다고 봐도 될까요
-
적으면 하루에 한시간 많으면 두세시간만 빼고 학교에 있는 시간동안 다 공부로...
-
기출에서도 정말 뜨문뜨문 나오던 주제인데 올해 수완에서도 에이젠슈타인 바쟁 나오고...
-
늦게 일어나니까 국어 시간에 머리가 안 돌아감..
-
타강사들 현장녹화에 비해 초반부에 이동하는 학생들 얼빡샷이 거의 매 강의마다...
-
논술접수 0
다음주 월요일부터 시작임? 낙지에서 하면 되나
-
관독 다니는데 감기랑 기침이 너무 심해서 이틀 연속 빼게 생겼네 아까운 내 시간.....
-
노베고 요번9모 4등급 후반정도 입니다. 4초반에서 3후반이 목표인데 사실 제가지금...
-
만약 대학에서 수능 과탐/사탐의 '개념'만 배운다고 생각할시, 보통 몇일정도 걸리는...
-
있으실까요...양이 너무 많을까봐 걱정되는디...
-
연대 교차 1
올해 사탐 가산점 때문에 연대 교차가 불리할 텐데 그래도 연대 이과대나 낮공...
-
21번 2
f'(x)의 정적분 형태로 계산하는게 가장 깔끔한듯 f(1) - f(-1) =...
-
얻어갈거 많고 기하문제 좋은 실모요
-
과탐인데 사탐런하라 하면 누워서 침뱉기고 사탐인데 사탐 오라 하는 것도 그사람이...
-
사탐런에 관해서 1
근데 사탐런하고 수능쳤는데 개념완성 부족해서 한개틀리고 실수해서 한개 더 틀려서...
-
수학조언좀 0
군수생인데 수학 컴팩트한 강의나 문제집추천부탁드립니다.. 시간이많이없어서
-
명확한 근거 없으면 (정확히 주어지거나 상황상 진짜진짜 명확한 경우빼면) 가정하고...
-
작년 9평을 능가하는 사상 최대 쉬운 난이도로 출제된 이번 9월 모의고사에서도...
-
수학조언좀.. 0
현재 공통 뉴런1회독에 수분감step1 2회독했는데 뉴런에서 배운거 복습할겸...
-
자연물이 슬퍼할 수 없고 분명 누군가의 정서가 투영되어야 한다은 것에는 동의하나...
-
현실이 된다..
-
22번 유기해도된다 해야한다 실모풀때나
-
할 말 없어서 쥐어짜낸 게 고작 “취미가 술담배”
-
국어 컷 뭐냐 2
22수능 재림인가
-
개념은 전과목 돌렸고 44344입니다..국어도 독서만 틀려서..갈길이 멉니다만..가능할까요..??
군대에서 코딩은 어떤 앱으로 하고 계신가요?