[C++][백준 4673][에라토스테네스의 체] 셀프 넘버 :: seoftware

문제

https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

에라토스테네스의 체

소수를 구할 때 가장 최적의 알고리즘이 "에레토스테네스의 체 Sieve of Eratosthenes"다. 

다음 그림을 보면 에라토스체네스의 체를 쉽게 이해할 수 있다.

에레토스테네스의 체

이는 2부터 시작해서 루트 N (sqrt(N))까지의 배수를 지워가는 방법이다. 어떤 수의 배수라는 사실은 그 수는 더이상 소수가 아니라는 의미이므로 소수 목록에서 제외시키는 것이다.  

코드로 나타내자면 대략 아래와 같다.

//isPrime 1부터 num 까지 true로 초기화
//에레토스테네스 체를 이용해서 배수는 false로 바꿈
for(int i = 2; i <= sqrt(num);i++) {
	for(int j = i+i; i <= num; j += i) {
    	isPrime[j] = false;
    }
}

소스코드

#include <cmath>
#include <iostream>
using namespace std;

bool selfNumber[10001];

void getNext(int x) {
	int thousand, hundred, ten, unit;
	thousand = x / 1000;
	hundred = (x % 1000) / 100;
	ten = (x % 100) / 10;
	unit = x % 10;

	int next = thousand + hundred + ten + unit + x;
	if (next < 10000 && !selfNumber[next]) {
		selfNumber[next] = true;
		getNext(next);
	}
	else return;
}

int main(void) {
	selfNumber[0] = true;
	for (int i = 1; i < 10000; i++) {
		if (!selfNumber[i]) getNext(i);
	}
	selfNumber[10000] = true;
	for (int i = 1; i <= 10000; i++) {
		if (!selfNumber[i]) cout << i << endl;
	}
}

 여기서는 소수를 구하는 문제는 아니지만 에레토스테네스의 체를 사용한다.

 getNext라는 함수에서 다음 수를 구한다음 해당하는 수를 true로 바꾸고 그 수에 대한 getNext를 반복적으로 수행하는 것이다.

 마지막까지 false인 수는 selfNumber이므로 false인 값의 i를 출력하면 끝!