컴공 일기 246
게시글 주소: https://old.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
비상경으로 여의도 증권사 취업 가능한가요? 잘 아시는 분 댓글 부탁해요!
-
과탐 3~4등급 받다가 사탐런 한 애들이 왜 과탐 1~2등급 애들한테 능지 딸리다고 하는거임?
-
개씹허수입니다… 두번째줄 파란글씨부터 왜 저렇게 나오는지 이해를 못하겠어요...
-
혹시 아시는 분 계실까요? 9평으로 업데이트 돼서 그런가 확인할 수 없네요
-
해도 상관없지? 줄여야해서 어떻게든
-
원래도 멍청하지만 귀마개 끼면 더 멍청해지는느낌.. 답답한거 같은느낌
-
분명 첫 문단에 "블록을 블록체인에 연결할지 여부는 모든 노드들이 참여하는 승인...
-
과탐러들 사탐은 개천절부터 시작해도 1 가능하다 진지하게 말하더니 진짜 좆되게...
-
수특 비문학 1
수특 비문학 주제복합 풀어보고 있는데 저만 어렵게 느끼는건가요?
-
화작기하생윤사문한문 Ret’s go
-
나는 그를 안다. 매일 의대 관련 뉴스만 벅벅 올린다. 그의 풋풋했던 수험 시절...
-
내년수능보는데 둘중 뭐를 더 추천하시나요?? 한지가 더 세지보다 어렵긴한데 세지는...
-
평가원 기출 그냥 그대로 실제 모의고사 용지 사이즈로 파는거없음? 영어기출...
-
[속보]복지부 “2026년 의대 정원 논의 가능…대화 문 열려 있어” 1
정부가 2026학년도 의대 정원에 대해 의료계와 논의가 가능하다고 재차 강조했다....
-
최저러라 탐구 투자 할 시간 많긴한데 겁나긴한다 이게 맞겠지...? 참고로 과탐4떳음..
-
정석 0
수학의 정석 기본편 한번만 보고 실력편만 n회독 해도 되나요?둘다 계속 n회독을...
-
형은 게이짓은 안해
-
여권용 증명사진 2장, 신분증, 응시료(결제방법은 응시처문의) 준비해서 서둘러 접수하십쇼
-
??: 각하!! 이번에 영어 1등급비율이 22%랍니다 3
이건 5.5%인데?
-
아주대병원 투입 군의관 3명 모두 '근무 불가' 의사…업무 중단 1
어제 마취과 1명·오늘 응급실 2명 투입됐지만 출근했다 돌아가 (수원=연합뉴스)...
-
하 평가원 선생님
-
과외 그만하게되면 연락 안 하나요?
-
국어 24번 4
2번선지에 화자가 북방을 떠나면서느낀 슬픔이라는게 허용되는건가요 ..?
-
안 한 지 너무 오래됐나
-
문과든 이과든 설대 못쓰죠?
-
미친놈처럼 달리면 수학제외 1211 가능할가여
-
그와중에 찍기 개못하네
-
가천의 아주의 1
어디가 더 인지도 ㄱㅊ음?
-
정법 질문 0
10번 ㄷ선지 판별할 때 B의 결정이 위헌인지 헌법불합치인지 어떻게 구분하나요?
-
아오ㅋㅋ
-
이거 원래 중대 문과랑 건대 이과랑 겹치는 거임? 아님 중대가 후한 거임? 내...
-
일단 지1 고정으로 박고 화1, 생1, 생2 셋 중 하나 할예정인데 진지하게 추천좀 해줭
-
1. 수능 때 국어가 어렵게 나올 거 같아서 훈련해보고 싶은데 기출말고 어려운 국어...
-
69평 1등급 나왔다고 수능 때도 1 나올 거라 생각하는 것 제가 그랬다가 9평...
-
수특 수완 다 끝냈고 기출책은 따로 수능 기출의 미래라는 책 풀었는데 이제...
-
ebs넘어가도 되나요? 당연히 안되겠죠?
-
수능 앞다리가 1이라는데 아닌데요 앞자리가 6이에요가 아니라 지금 수능 전나리었지...
-
초코우유 원탑은? 둘다 먹어보신 분만 투표 부탁드려요 ㅎㅎㅎ
-
수능때 3,4등급 목표면 노베인 사문하기보다는 생2 유지가 나음? 사문이 2달하면...
-
1. 개어렵지만 경쟁률 낮은 숙대 2.비교적쉽지만 경쟁률 높은 동국대나 세종대
-
이원준T 9평 해설 특강 신청햇는데 자리예약 따로 안해도 대나요? 현강을 가본 적이...
-
국어특 8
시간은 남는데 채점하면 엄..
-
과탐 5~6등급이 능지문제일 가능성도 있지만 과학에 흥미가 없음>>공부를...
-
지금부터 하루에 하나씩 수학 실모 푸는거 어케 생각하시나여 8
9평 68점...(확통 1틀)이고 6시 이후로는 수학만 할까 생각입니다 국영탐으로...
-
싸우지마세용 37
친하게 지내용
-
전국 의대 전국 치대 전국 한의대 전국 약대 전국 수의대 서울대 자연계열 전부...
-
그래? 알엔디 한번 삭감했더니 문과에 인재들이 몰리네!
-
언미물2화2러
-
고민임 원래는 교대 가고싶었는데 요즘 워낙 말이 많아서.. 6모는 서성한 낮과 9모 연고 낮과 나옴
군대에서 코딩은 어떤 앱으로 하고 계신가요?