컴공 일기 246
게시글 주소: https://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를 선물하세요.
-
두과목 번갈아 가면서 하시나요 아니면 같이 하시나요 탐구가 부족한편인데 하루 2시간은 해야겠죠
-
중앙대 영화과에 정시로 꼭 붙고 싶은데ㅠㅠ 다들 어느정도 등급(백분위)로...
-
30분정도를 개지랄을....
-
진심 맨날 띵가띵가 놀아도 수능1 찍는 씹재능러 존나 부럽다
-
진짜모름
-
미적선택인 재수생입니다 제 실력은 6모 59점 7모 61점으로 50-60점대의...
-
수리논술 준비하고 있는데 확통기하 거의 노베입니다 개념 대충 알아요 지금 다니는...
-
10만원대 우산을 본인꺼 마냥 자연스럽게 가져가고 사과 한마디 없이 돌려준...
-
수학 공부 0
제가 지금 미적분을 하는데 하루에 수학9시간투자해서 수1 수2 미적 다 3시간씩...
-
실제로 평가원이나 수능모고에서 p% 퍼센트포인트 단위로 문제나온적있음?? 한번도 없는거같은데
-
제발치려무나 ㅅㅂ
-
궁금한 것 남겨주세요. 세세한 거라도 좋습니다. 대학생활 / 컴공 관련이면...
-
저녁 ㅇㅈ 6
-
파이널때도 수능단단 같은 ㅂㄹㅈ 책 품???
-
트럼프 측근 “한동훈 브라보…美외교정책과 일치하는 훌륭한 방향 제시” 1
엘브리지 콜비 전 미국 국방부 부차관보 韓후보 전당대회 토론회 영상 SNS에 공유...
-
1. 개념을 완벽히 잡고 그때까지 문제를 안 풀고 다 잡으면 문풀 2. 개념을...
-
언매 감 잡아가는중!! 오분후식
-
가정사때문에 집애서 쉬지도 못하네 아오 동생시치ㅋㅋ
-
브롤스타즈하는데 옛날 내 모습 보는것 같네 귀엽당
-
그러면 너 또 2군행이야
-
다들 어땠음뇨? 현재 고2임 학원에서 서바 브릿지 전국 줘서 푸는데 브릿지...
-
씨발련... 오늘은 내가 졌다...
-
선택과목으로는 확통 선택할건데 수학 3등급 맞으려면 전략적으로 어떻게...
-
메인글보고 든 생각인데 이렇게 사니까 오히려 편한듯 0
뒤에서 하고싶은말 남 까고싶은말 면전에다가 대고 하고 남들 다 눈치보면서...
-
진짜 힘들어 보임
-
푯대를 향하여 0
-
15회분이던데 물론 많아서 좋기는한데 왤케 증가한 느낌이지 작년에도 오프기준 15회차였나요
-
이번 뇌는 오래 썼어
-
그래도 강사컨 많지 않나 본인 메가재종 다니는데 여긴 그딴 거 없음
-
요즘 사설만 벅벅 풀다 뇌오염된거 같아서 5개년치 기출 킬러만 다시 보고 있는데...
-
기출 풀 때마다 늘 29 30은 읽어보지도 않고 포기하는 처지라...확통런마렵다ㄹㅇ...
-
"chatGPT 4o"의 영문법 실력이 궁금하지 않으세요? 독해학교가...
-
팝콘 맛있네용
-
한화는 항상 수비가 너무 아쉽네,,
-
그냥 수도권에서는 해커스 가면 되나요,,?
-
천사표 이별은 없잖아~ 너만을 기다려는 인형은 아냐
-
!!!!! 갓성비자나
-
혈육이 물건 다 집어던지고 집안 개판내서 여기로 피신 옴 조용한 통유리실에서 에어컨...
-
국어 실모 개수 0
몇 개가 적당한가요?? (상상 17회, 이감 17회, 김승리 3회 있어요) 부족하면...
-
학교마다 다른가
-
아니 시대랑 강대 모고는 안 팔더라도 양심이 있으면 국어는 상상 수학 킬캠 이감...
-
미적의 신이 되고파
-
시발
-
기울기를 이용하지 않고 푸는게 기울기 이용한거보다 어렵나요?
-
드릴5랑 비슷하거나 약간 더 어려운 둣
-
슬프다ㅠㅠ 다행히 결과물은 나쁘지않다 셤 끝나면 머리 제대로 다시할거야
-
하 오늘 대치 0
은마사거리에서 버스타는데 학부모님들 차 다 세워놓고 차 개막히니까 버스가 차선도...
-
지금까지 남르비라고 속여 죄송합니다.
군대에서 코딩은 어떤 앱으로 하고 계신가요?