컴공 일기 246
게시글 주소: https://i.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를 선물하세요.
-
사탐이야 그냥 다풀고 느긋하게 벅벅 쓰면 되고 과탐러들은 마킹에다 가채점까지 하면...
-
이번 9평 윤사 19번 제대로 설명할 수 있는 사람 있음? 8
ㄷ 선지가 강사들 해설을 들어도 하나같이 ‘이통하고 기국은 상관 없다!’는 식으로만...
-
밥 먹고 와서 지금 들어야하는데 지금 들으면 독서는 11시 30분에 끝나고 문학은...
-
아래쪽에 있는(B에 붙어 있는) 부정합이 경사부정합인가요 난정합인가요? 아니면 둘 다 해당인가요?
-
생1버리기 4
생1 스킬편 이제야 가계도까지 다 들었고 비분리는 1도 안 들었는데 비분리,...
-
레어 다 사려면 7
1억더코만 있으면 되는데 빌려주실분 구해요
-
옥텟법칙 질문 0
학교 선생님께서 확장 옥텟법칙을 프린트에 넣어 놓으셨는데 찾아도 잘 안 나와서......
-
혹시 예를들어 각 강사의 수학 n제가 매년 모든 문제가 다 바뀌는건가요? 아니면...
-
일단 나.. ㅎ
-
지금까지 했던 게 다 의미가 없어질까 봐
-
오늘 9더프 국어풀다 느낌 슬슬 기출 기억 안나기 시작하니 기출 샤워가 필요해!!
-
어제 과외 수업 바꼈다고 했는데 오늘 기다리고있었네
-
3일전부터 그냥 아무것도 하고싶지가 않고 눈에 아무것도 안들어와요.. 독서실에서도...
-
위험하네요
-
기출 vs n제 20
이제 뉴런 다 들었는데 아직 기출이 0회독이라 기출을 해야할지, 아니면 뉴런이...
-
하아 다시 기출 할까요
-
술에 취한 수험생이 별안간 언성을 높입니다. 어, 어. 보고 가믄 돼. 다시!...
-
수능날 1 떠야되서 마음이 심란해짐.......
-
기적의 1빙고 ㅋㅋㅋ
-
여친구함 10
ㅈㄱㄴ
-
오르비하는 사람이 제 이상형임..
-
사바사일텐데 공부는 너무 하기 싫고 그냥 수학 기출이나 돌리려는데 노래 안 들으면...
-
물리좃댐 2
배기범모 34점 31점 개좃박았음 근데 혼자서 풀어봐도 못풀겠는 문제가 두개씩 있음...
-
이감 시즌6 등록했는데 아직 일정표에 안나와있어서 그러는데 저번 실모시즌 때 몇까지...
-
수능날 역통수로 8
언매 98 95 92 화작 100 97 93 미적 96 92 88 기하 96 92...
-
츄라이 츄라이
-
한완수vs뉴런 2
한완수를 하면 상중하를 다해야하는건가요?? 공통이랑 미덕 다할생각입니다
-
ㅇ?
-
9월 덮도 추가 신청 받던데 10월 덮도 추가신청 받을라나
-
중3이 여러분 앞에서 이런 말 해도 되는진 모르겠는데 29
인생 어떻게 살아가야 하죠
-
킬캠 아낄까 1
4개 남았는디
-
님들 탐구1 탐구2 사이 2분동안 탐구1 가채점표 써도되나요 11
생지라서 생명은 시간이 잘 안남네요
-
둘이 손잡고 나가이씨
-
정시공부했던 것을 떠나보내기도 싫다
-
간쓸개 풀다 보면 가끔 이감이 문제를 이상하게 내는 건지 그냥 양치기만 하다가...
-
여론조사 2
기타는 댓글로
-
자전거타고 10분거리라 하루에 3번씩 왔다갔다 하는거 생각하면 그냥 집에서 공부하는게 나으려나...
-
사실 어차피 버릴 시간 공부에 쓴다는 것만 보면 메리트가 커보이는데 그만큼 뭔가...
-
고3 결석 질문 1
질병결석하면 처방전 필요하잖아요? 전에 받아뒀던 처방전 복사해서 날짜만 바꿔서...
-
화1 50 (시간 25min) 수특 수완에서 생각보다 연계많이됨(20번 18번)....
-
시간낭비죠…?ㅠㅠㅠ 머리로는 알고있어서 자꾸 현타와요
-
옯창 빙고 ㅇㅈ 2
오르비에 상주하는 이유 오르비없었으면 불안해 죽을 예정이었기 때문
-
딱 1년 남았네요 이제 말출포함하면 1년이 아니긴 하지만요 ㅋㅋ 근들갑 떨지 않고...
-
흠 2만 풀까
-
시ㅣ발 섹ㄱㅅㅅ스ㅡ ㅅㅅㅅㅅㅅㅅ
-
수능 잘나오면 노베 후배들 상대로 수능준비반 해보고싶다 7
누굴 가르친다는거 ㅈㄴ 재밌고 설레는듯
-
물리2 강K모고 난이도 다른 실모에 비해 어느정도 인가요?? 너무 어렵던데..
군대에서 코딩은 어떤 앱으로 하고 계신가요?