컴공 일기 246
게시글 주소: https://i9.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
볼때마다 아 써야지 하는데 막상 문제 만나면 ..? 이거 뭐 써야했더라 로 인식됨...
-
걍 갈아서 플로우나 숏컷에 넣고 전국서바나 주지 무슨 삼도극 프랙탈 든 실모를 그대로내놓냐 쯧...
-
영어 문제 시간 0
한문제당 몇분 몇초 정도 재고 푸는게 좋을까요
-
하 3
이제 1주일
-
딱 평가원난이도~평가원대비 4점 낮아질정도 수학실모 뭐가 괜찮음?
-
저 놈 왜 안사라지는 거임 왜..? 무지성으로 기함수 싹다 날렸는데…
-
이땐 진짜 하루에 10시간 이상 메이플했었는데 올해 1월이 신창섭이 리부트 죽여서...
-
천만 덕코 드림 4
10M xdk dream
-
공부나해야지 0
카공가자
-
요즘 술 익는 집 보는데 너무 재밋음
-
여긴 수험생 갤이니까 공부하려나
-
수특은 가격이라도 싸지
-
ㅇㅇ
-
쉬운 수학 실모 1
추천 해주세요 오르비 기준 말고 진짜 쉬운 실모로용
-
해강 보시나요? 아님 해설지로만 오답하고 끝?
-
취미가 덕코모으기면 데요
-
오늘 할거 0
1.수학 쉬운 실모 하나 풀고 기분 좋아지기 2.국어 3지문만 풀기 3.탐구 실모...
-
어디있었는지 까먹어서...
-
우리나라에 생각보다 의치한약수로 먹고 사는 대학이 많음 4
그냥 생각해보면 답 나옴
-
볼륨도 작은데 그냥 대학교에서 배우는 정도로만 해도 충분할 것 같은데 차라리 확률을...
-
송편 맛있네 1
-
근데 왜 앞에 B안달려있지
-
간호학과, 국립대, 인서울도 미달 ㄷㄷ
-
70% 컷이 2.11인데 2등이 2.11이라는 건가요!!??
-
6평치고 지구 시작해서 현재 유자분이랑 oz basic모고 레벨2 진행중입니다. 한...
-
A,B,C의 좌표를 다 구해서 AB와 AC의 같음을 이용해 두점 사이의 거리 공식...
-
이감vs한수 0
국어 교재를 한 지문씩 끊어서 풀면 점수가 잘나오는데, 80분 잡고 이어서 풀면...
-
분명 처음 증원됐을때만 해도 정부가 쓰레기고 의사는 피해자로 보였는데 요즘...
-
현대로 보면 솔직히 맞지 않나
-
갠적으로 밀린실모는 파는것보다 기부하는게 더 편한듯 0
하나도 안귀찮음 이번에 삼수하는 친한 동생한테 강사모 몇개 줬다니 좋아해서 내가 더 기분이 좋네
-
잠만 계속 잠
-
'예컨데 실질 임금은 명목 임금에서 물가변동분을 뺀것 임에도 불구하고' ->...
-
대부분 질문 내용에 본인이 필요한 공부가 뭔지 써있음
-
정확한 풀이를 모르겟다
-
대성인데 ㅇㅇ
-
EBS좀 보다가 “달러화가 전 세계에 공급되기 위해서는 미국의 국제수지가 계속...
-
실시간 열받아서 4
케로로 초코칩 쿠키 먹을꺼야
-
수능이 다가온다는 의미겠지 수능날 개같이 지워야지
-
내 텅장 5
올해초엔 분명.... 갑자기 현타오네 재수비용 ㅆㅂ이...
-
ㅎㅎ..
-
13틀 진지하게 못풀었음 뭔가 예상되는 방향에서 계산이 안됨 다른 길이 안 보여서...
-
진짜 어렵네요.. 글을 앞으로쓰는건지 뒤로쓰는건지 뭐라고 쓸지는 알겠는데 무슨...
-
에너지드링크 ON
-
스카 6층인건 4
담배를피지말라는건가...흠
-
10만원짜리 패드로 인강 듣고 있는데 나중에 피뎁 쓸 일이 많아 보여서,,
-
급함
-
갈아만든 ldH 1
군대에서 코딩은 어떤 앱으로 하고 계신가요?