컴공 일기 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를 선물하세요.
-
웃통 벗고 동생 옆에서 오르비 중 백수 그 자체
-
이거왜이럼 러셀 1
이거 왜 로그인하면 외부생 이퀄모의고사 신청도 안돼요?
-
중국 입장에서 신의 한 수 군인들을 많이 잃었지만 그에 비해 전략적으로 얻은게 너무...
-
싸가지없음
-
뭐 푸는게 좋을까요??? 6모 47 나왔습니다
-
덥다
-
높5만 나와도 언매 개념하면 3,4가능 할지도 모른다 생각하니 의욕생긴다. 높5만...
-
1. 혼잣말하는 난해한 상황을 강아지에게 말을 건냄으로써 자연스러운 분위기로 전환....
-
고1 정시 수학 1
현재 김기현 기생집 2,3점 풀고 있는데 앙이디어 기생집 4점 따라가는게 좋을까요?...
-
강기원 프리뷰 1
대체 프리뷰 시험지가 어딨나요 하
-
말로만 듣던 장수생이 되겠다
-
( 국민 '필수의료강화해야+의사수 늘려야' --> '건강보험료는 인하 또는 동결해야.' ) 2
국가에 바라는 건 많지만 관련 세금은 못내겠다. 아름다운 스탠스임.
-
버근가
-
국어 > [리트 전개년 기출 언어이해] 예비 2009 11~13 > [리트 전개년...
-
기시다 후미오 아이젠하워 마윈 히틀러 처칠 세상은 삼수생이 바꾼다
-
"나르시스트를 피해야 하는 10가지 이유" "당신은 소중하니까 어쩌고" 이거보고...
-
아어어엉양 9
어어어ㅓ구구
-
님들의선택은?
-
ㅇㅈ 16
하니나 보고 가라
-
탈조선은 ㄹㅇ 능지순
-
방학중에 딱 하루만.. 대신에 다른 날에는 그날 하루분량은 다 해냈다면 괜찮지...
-
6일동안은 인강 듣고 4일동안은 천천히 정독하면서 복습문제 풂 사탐은 신이야
-
진짜 할복함 2
ㅂㅂ
-
어떰요
-
8월전까지 끝내고 수특수완기출 풀면서 아리까리하노? 싶으면 개념서 찾아서 정독하고...
-
있나요
-
나만어려움??????? 2회 푸는데 14 15 턱막히더니 21 케이스 하나 빠뜨려서...
-
재수 시작한 이유도 진짜 온힘을 다해서 공부해본적이 없는거 같아서 아쉬워서 했는데...
-
드릴5 난이도 7
이해원s1 회차당 1~2개씩 틀리는데 드릴5 들가도 됨? 아님 딴거 풀고 들어가는게 나음?
-
꽤 색다름. 나는 지금까지 문학을 푸는데에 정형화된 방법이 없었는데, 문학을 대하는...
-
와 진짜 억울하다 16
강k 3회 28번 시간부족으로 못풀고 나머지 다 풀었는데 7 9 22 27 계산 실수로 날려먹음..
-
수학 엔제 어려운걸로 추천좀 저번에 설맞이 추천받아서 풀어보니까 그냥 그렇던데...
-
병호쌤 교실은 안추웠는데
-
결말) 775 나와서 카투사 입구컷당함 ㅅㅂ
-
군, 북 오물풍선 잇단 살포에 대북 확성기 방송 전면 시행키로 1
[서울=뉴시스] 옥승욱 기자 = 우리 군이 21일 오전 북한의 9차 오물풍선 살포에...
-
D-480 계획 4
36859 노베 오늘 계획 윤혜정 개념의 나비효과 14강 워크북 풀기
-
패스없는데 문해전 강의 안듣고 독학용으로 쓰는건 별로인가요?
-
매일 두세번은 쥐나네 시벌…
-
첫시험도 원래 아쉬운게 맞죠?
-
'건물주' 남친과 결혼 고민하는 20대 여성 "생활력이 걱정된다" 8
(서울=뉴스1) 김학진 기자 = '건물주' 남자 친구와 결혼을 망설이는 20대...
-
수학 커리 0
이미지 선생님 미친 개념 들으면서 마더텅 기출 혼자 풀고 6모 (미적분) 백분위...
-
자살하고 싶은 군생활이다
-
왜다들 이상한말만하고!!!!!!너무하시내요진짜 그래서 박광일 요즘 강의하나요
-
제 풀이법이 뭐가 틀렸는지 모르겠어요 맞게 푼 것 같은데… 정답은 288입니다
-
수학 4면 0
개념 한번 빡 듣는거 괜찮을까요 학원쌤은 부딫혀보라해서 학원 자체 모고 오답하려해도...
-
일반적인 구청,시청 공무원은 어떤 과목을 공부해야하나요? 완전 노베인데 과목별...
-
아 할복해야지 4
군대에서 코딩은 어떤 앱으로 하고 계신가요?