컴공 일기 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를 선물하세요.
-
문제에서 ㄱ보기가 옳다고 되어있는데 사내 동호회는 공식조직이 아니고 자발적 결사체...
-
지구에서 움직이는 우주선의 시간을 측정랄 때 지구의 시간은 지연된 시간이고 우주선의...
-
수특에 이렇게 나와있는데 그래서 답이 왜 3번인 거죠? 맨틀 위에 떠 있는 지각이래매...
-
지금까지 정부 스탠스상 진짜 당장 목에 칼 안들어오면 무조건 시간 끌거라고 봄...
-
소요 시간 72분 93점(독서 -5 문학 -2) 난이도는 6모랑 대비해서 독서는...
-
요새 강남 대치 부모님들 수능 성적표 달라고함? 과외힐때 3
보현사건땜에 달라하나? 이제
-
상남자 특 3
듄 연계공부 안함
-
문학 << 불 언매 << 불 비문학 << 가나형에 난이도 몰빵이 메타인건가 다 그런 느낌이네
-
파일 받아서 풀어봤는데 62점 나왔어요 교육청, 평가원에서는 대부분 2등급 받았어요...
-
잇올같은데 10월말 11월초에 3주정도 등록가능한가요..? 0
혹시 저때 등록해보신분 계신가요..?
-
몇 개 정도 푸시나요? 지금 구매한 게(상상, 이감, 김승모) 35~6회 정돈데 더...
-
아
-
스카 너무추워서 5
알래스카온줄 하하하
-
그래도 8시간은 했네..
-
굿
-
어려운 27번 정도임?
-
멘탈관리법 1
여러분만의 멘탈관리법+정신건강유지법 공유해주세요..
-
이게 제일 어려운 듯 발표 중에서 자료 없이 쌩으로 5분 하는 게 존나 어려움...
-
꿈속에서 시간을10시로 착각해서 겁나 놀래가지고 진짜 일어났는데 아침8시였다
-
언매질문 3
왜 ㄱ 에 2,3번이 맞는게 아니라 1,4,5가 맞는건지 아무리 봐도 모르겠음 묻-...
-
기대기대
-
느낌이 옴
-
문학 인강 1
올오카 문학을 들었는데도 문학을 너무 못하고 문학은 김승리쌤이랑 안 맞는거 같아서...
-
훌륭한 마법사가 되겠어~
-
원하는 조건은 1. 특정 앱 몇개만 잠금or 특정 앱 몇개 제외하고 전체 잠금 가능...
-
강원대 의대 조사해보니 티오(?)도 낮고, 인기과 가기 힘들다고 하더라고요. 그래서...
-
와잉감자 부활 3
헿
-
고2입니다 이제까지 영어공부 제대로 해본적이 없구요 중학교때 부터 영어를 놔서...
-
서바 답지 0
서바 생명 라이브 듣고있는데 아니 답을 안알려주는데 어떻게 아나요??? 2회 답 알려주실분 없나요
-
언매 퀴즈 13
'강마르다'는 강조의 의미를 가진 접두사가 붙은 동사이다. (O, X)...
-
1번 자리- 옆뒤로 사람들 있음(성인 자격증,취업 준비로 추정됨) 2번 자리-...
-
나비효과 독서 0
이거 지금 봐도 딱히 의미 없을 것 같네 내가 직접 공부 좀 하고 문풀 어느정도 한...
-
기출을 아직 못돌려서 너기출이랑 같이 할 거를 찾고 있습니다. 현재 김기현 아이디어...
-
삼겹살이나 구워서 불닭이랑 같이 먹어야지
-
. 1
머리를 잘랐는데 이상하네 기분이 안좋어..
-
ㅈㄱㄴ
-
2.7 반택 9월달분까지만으로 팝니다 진짜
-
ㄹㅇ 역대급 시청률 가능아니냐 둘다 21세기 우승 없는채로 만나야함 멸망전으로...
-
기출분석할까 0
기출 분석은 안하고 1회독했을때 6모봤는데 미적 백분위95뜸 기출분석을 할까 아니면 n제나풀까
-
사탐 옳은 것을 모두 고르시오로 문제나오면 어케될까 7
20문제 전부 ‘옳은 것을 모두 고르시오’ 이렇게 해서 1개에서 4개까지 답으로...
-
기아 엘지 두산 크트 쓱(아니면 삼성) 크트 무조건 올라간다고 본다 쓱 아니면 삼성인데 모르겠음
-
문학이랑 선택은 어느정도 괜찮은데 독서는 그냥 순수 독해력 문제인거 같은데 어떻게 해결해야하나요?
-
웃통 벗고 동생 옆에서 오르비 중 백수 그 자체
-
이거왜이럼 러셀 1
이거 왜 로그인하면 외부생 이퀄모의고사 신청도 안돼요?
-
중국 입장에서 신의 한 수 군인들을 많이 잃었지만 그에 비해 전략적으로 얻은게 너무...
-
싸가지없음
-
뭐 푸는게 좋을까요??? 6모 47 나왔습니다
-
덥다
-
높5만 나와도 언매 개념하면 3,4가능 할지도 모른다 생각하니 의욕생긴다. 높5만...
-
1. 혼잣말하는 난해한 상황을 강아지에게 말을 건냄으로써 자연스러운 분위기로 전환....
군대에서 코딩은 어떤 앱으로 하고 계신가요?