컴공 일기 246
게시글 주소: https://app.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를 선물하세요.
-
최상위권만 손해지 대부분 기회의장 아님?
-
제 풀이 문제점이 먼가요?
-
사람이 꼭 누군가를 좋아해야만 살아가는 것은 아니잖아 0
누군가를 좋아하는 마음이 없어도 살 수 있어 사랑받지 않아도 살 수 있는 것처럼...
-
수능 접수 완 2
화작미적지1물2
-
사문 지구 커리 1
사문 44(1,2,16번 틀) 지구 44 (16,19 틀) 지구는 크로녹스랑...
-
저만 반수할래요
-
진짜 궁금해서 묻는데 사탐 1-2달 만에 1가능이면 8
나머지 96%는 뭐하는 사람들이에요?
-
22때부터 수학은 불이 없었는데 올해는 불일듯...ㅋㅋ
-
고2 9월 29번 분석입니다.
-
지금 현재 박선 단과 다니고 있는데 사실 제 실력에 비해 너무 지엽적인 부분만 알려...
-
확실히 인물이랑 다 기억나면 지문 제끼고 바로 문제로 가시나요?
-
국어 불수능 5
만유ㄴ력 질점급 나올 가능성도 있음?
-
추천점요 강의말고 교재로 다 해결할 수 있음좋겠음
-
진짜로? 심장 개터질듯 네 저 지금 터지기 직전임
-
추경호 "2026년 의대증원 등 의료개혁 원점 논의 가능" (naver.com)...
-
국어에서 어느 입장을 근거로 다른 입장을 비판하는 문제가 약한데 극복방법 좀 알려주세요
-
랜만오입니다 1
연애고민 들을 분
-
내가 병신인가.. 국어 개병신은 아닌거같은데.. 백분위기준 (화작임) 작년 96...
-
과외때문이라고 대충 둘러대기.. 대충 두달 반 남았내여 70일의 전사 두가자
-
사탐런 하는 명확한 이유임
-
현장에서는 일상을 지내다가 또 한가지 아득했던 새로운 옛날의 기억이 떠올라 이제는(...
-
교과를 쓸까요 말까요.. 내신 2.4고 교과 쓴다면 국민대써야돼요.. 수능에서 너무...
-
지금이라도 뭔가 인강을 듣는게 나을까요 그냥 제 선에서 선지판단이나 지문 읽는...
-
1시부터 10시까지라니..
-
재수때해봣는데수능이가까워질수록어지러워졌던거같음
-
선택하고 독서2지문 풀고 시간봐서 가나부터할지 문학부터 할지 고민인데 비추하시나요?
-
사탐런 하지마라 1
도망친 곳에 낙원은 없다
-
메가패스보유하고있으면 서로 교환해요.. 33만원 아까워..
-
그리고이제 경제도 5자리수
-
안녕하십니까 9평 정치와법 중 법학 파트 해설 유튜브 영상입니다. 문제풀이 접근...
-
일단 수능은 멘탈 싸움일듯 ㅋㅋㅋ 저 그냥 씹유리멘탈인데 9평 끝나자마자 마음먹음...
-
현타와서 0
이번 9평 98 96 87 45 45 (학원에서 외부생으로 응시) 수험생들이 과탐을...
-
'삼형제 아빠' 덮친 음주운전자는 의사…"열심히 기도하겠다" 1
[헤럴드경제=김성훈 기자] 낮에는 꽃집 운영, 밤에는 대리운전을 하며 홀로 아이...
-
인서울 어디라인이라고 볼수있음? 이과 기준으로
-
수능 물리학1 예상 13
6모 9모 난이도 자체가 쉬웠긴 하지만!! 전기력 정량, 역학의 난이도 약화에 묻힌...
-
공대기전 어디라인임?
-
가을맞이 일기 한편...
-
요새는 사탐런이니 뭐니... 떼잉 평가원은 반성해라 좀
-
과탐보다 훨씬 수월한건 사실이지만 그렇기에 더 사소한 실수로 나가떨어질 확률도 크죠...
-
흥 너무해 0
ㅠㅠ 공부나 할게
-
걍 만백 100 나오게 내주면 아무 원성도 없을텐데
-
가기전까지 휴강인지 아닌지 모름
-
원래 국어 고정 1이긴합니다 작년 69수능 전부 백분위 99 올해도 6 백분위 99...
-
4000부 판매돌파 지구과학 핵심모음자료를 소개합니다. (현재 오르비전자책 1위)...
-
마지막 0
9모 언매 35 36틀렸는데 화작 풀어보니 12분쓰고 하나 틀렸습니다 ㅠ 언매 계속 하는게 맞을까요
-
헉… ㅋㅋㅋㅋㅋ 사탐 유지만 하자 이제 (물론 국수는 더 올려야 함)
-
뭐가 문제지 진짜
-
기출 풀다가 지문 겁나 길어서 ㅅㅂ 뭐지 싶었는데 열심히 읽다보니.. 그 악명 높은...
-
지2 생2 난이도 11
뭐가 더 낮아요
-
보닌 21수능 물1을 잊을수가 없다 1회독 15분만에 끝나고 틀리면 ㅈ된다는...
군대에서 코딩은 어떤 앱으로 하고 계신가요?