컴공 일기 246
게시글 주소: https://m.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를 선물하세요.
-
타인의 고통을 너무 쉽게 흡수해서 자신이 고통스러워짐
-
졸리다
-
D-30 0
세계지리 37 / 27-32 국어 28 / 2 사회문화 37 / 4 5 6 파이팅
-
이거 더프 성적푠데 이거로도 되나?
-
독서 -2 (어휘 17번 뭐지) 문학 -0 언매 -2 96점. 1컷 87 아니근데...
-
아가기상 2
ㅇㅇ
-
나왜 이륙함 0
근데 별개로 메가 교재비 얼마썼는지 찾으니까 책값만 260이노 ㅅ1발 ㅋㅋ 패스 2년치 제외임 ㅋㅋ
-
한 달간 올해 1년치 더프 구매해서 풀 예정인데 괜츈음? 2
알바해서 모은 돈으로 더프 1년치 이제 사서 풀려함 문제 퀄 어떰?
-
지하철에서 가방이 앞으로 안매짐..ㅠ
-
으헤~
-
않되..ㅠㅠㅠ
-
원래 10분이었으면 갈 거리를 20분 처걸려서 감
-
잠이 오는데 0
개망핶노
-
특모 시즌2 > 특모 시즌1 >> 배모 시즌 2>>>>>>>>>>배모 시즌1 이렇게...
-
ㅅㅂ
-
다들 화이팅!!
-
지구 문제풀고 모르는거 나오면 따로 노트에 적나요? 1
실모나 n제 풀면서 모르는 개념 나오면 전부 노트에 적나요...?
-
어기적 어기적 걷지좀 마라 시바
-
공간팽창 설명할때 풍선을 쓰잖음 풍선을 손가락으로 눌러서 생긴 구덩이가 블랙홀이고...
-
영어모고순위좀 0
영어모고를 잘모르겠어요 괜찮은거추천좀요
-
마침 삭제하긴 좀 그래서 곤란했는데 무히려 좋네요 저걸 마지막으로 남캐문학 공장...
-
독서실 도착 4
오늘도 화이팅하세요
-
안녕! 5
인사하면 받아줄겨?
-
급똥 ㅅㅂㅅㅂㅅㅂ
-
오늘계획 이감 6-5 킬캠 2-3 띵학모 2회 Oz 3-4 적중예감 3회 +a
-
다들 ㅍㅇㅌ 1
현역도 현역 아닌 옯붕이도 한 달만 버팁시다
-
머가낫나요
-
아예 안 보이게 할 순 없는걸까요?ㅠㅠ
-
저도 센츄 받고올게요(실력안됨)
-
블랙홀에 들어가서 거리가 거의 0에 가까워진 물체끼리의 중력퍼텐셜 에너지는 무한,...
-
가보자고
-
저도 일요일날 볼듯 난이도 적당하고 배울거 많았으면 좋겠네요
-
좋은 아침이에요 4
국어 예열을 시작하지
-
돌멩이와 돌멩이 사이의 거리가 1cm일때 중력퍼텐셜 에너지가 -3이라고 하면...
-
10월 학평 잘 보고 오겠습니다
-
??
-
최댓값 구하는걸 하..
-
파전 구워먹어야겠노 캬
-
Iq테스트가 훈련으로 개선되는 건지는 몰라도 괜히 쓸데없는 노력 퍼부으면서 절망에...
-
강심장 ON 4
-
자세한 건 말 못하지만 본인이 관심있는 학원 이름 디시에 서치 한번 해보고 가세요
-
진로 이런거 얘기하다가 영상쪽은 AI가 거의 대체할거라면서 나보고 잔인하지만 꿈을...
-
전건과 후건이 모두 참이라서 명제가 참 둘사이에 인과관계는 없다고 함 하지만...
-
### 1. **탄소 순환 (Carbon cycle)** - **뜻**: 지구의...
-
?
-
할루 4
-
블랙홀때문에 우주팽창이 이루어진다는 말을 어디서 들어봤음
군대에서 코딩은 어떤 앱으로 하고 계신가요?