[백준] 에라토스테네스의 체 기초 문제풀이 - 1978, 1929, 6588, 4673

1978 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

풀이

1000까지의 모든 숫자에 대해 소수인지를 미리 판별해놓고 입력이 들어왔을 때 소수면 카운트해준다.

#include <iostream>
#define MAX 1001

int a[MAX];

int main() {
    //1은 소수가 아니므로 따로 판별
    a[1]++;
    int n, tmp, result=0;
    scanf("%d", &n);
    for(int i=2; i<MAX; i++) {
        for(int j=i+i; j<MAX; j+=i) {
            if(a[j]==1) continue;
            else a[j]++;
        }
    }

    for(int i=0; i<n; i++) {
        scanf("%d", &tmp);
        if(!a[tmp]) result++;
    }
    printf("%d", result);

    return 0;
}

---

1929 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

 

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

풀이

m, n 범위를 입력받고, n까지의 숫자에 대해 미리 소수 판별을 해놓은 후 m부터 n까지의 소수를 출력한다.

#include <iostream>
#define MAX 1000001

int a[MAX];

int main() {
    a[1]=1;
    int m, n;
    scanf("%d %d", &m, &n);
    for(int i=2; i<=n; i++) {
        for(int j=i+i; j<=n; j+=i) {
            if(a[j]==1) continue;
            else a[j]=1;
        }
    }
    for(int i=m; i<=n; i++) {
        if(!a[i]) printf("%d\n", i);
    }


    return 0;
}

---

6588 골드바흐의 추측

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

 

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

 

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

 

풀이

최대 범위까지의 소수 판별을 미리 해놓고, 홀수 포문을 돌며 소수들로 주어진 수를 만들 수 있는지 확인해서 출력한다.

#include <iostream>
#define MAX 1000001

int a[MAX];

int main() {
    // 홀수 소수만 0을 가지고 있게
    a[1]=1, a[2]=1;
    int n;
    for(int i=2; i<MAX; i++) {
        for(int j=i+i; j<MAX; j+=i) {
            if(a[j]==1) continue;
            else a[j]=1;
        }
    }
    while(1) {
        scanf("%d", &n);
        if(n==0) break;
        bool find = false;
        for(int i=3; i<=n/2; i+=2) {
            if(a[i]==0 && a[n-i]==0) {
                printf("%d = %d + %d\n", n, i, n-i);
                find = true;
                break;
            }
        }
        if (!find) printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}

---

4673 셀프 넘버

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

입력

입력은 없다.

 

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

내 풀이

10000까지 생성자가 있는 숫자들을 지우고 출력한다.
생성자로 구한 숫자가 이미 체크한 숫자일 때는 그냥 넘어가도록 if문을 걸어도 되겠지만, 이미 생성자로 숫자를 구한 후이기 때문에 배열을 확인하는 시간과 숫자를 배열에 넣는 시간이 크게 차이가 나지 않을 것 같아 따로 넘어가는 코드를 넣지 않았다.

#include <iostream>
#define MAX 10001

int a[MAX];

int main() {
    for (int i=1; i<MAX; i++) {
        int tmp=i, sum=i;
        while(tmp != 0) {
            sum += tmp%10;
            tmp /= 10;
        }
        if(sum>MAX) continue;
        a[sum]=1;
    }
    for(int i=1; i<MAX; i++) {
        if (a[i]==1) continue;
        else printf("%d\n", i);
    }

    return 0;
}

 

다른사람 풀이

생성자에서 구한 숫자가 다음 생성자로 이어질 수 있도록 수열을 구성했다.
(그런데 이중포문을 돌면서 소요시간이 좀 더 많아지는 것 같다. 이런 아이디어도 있구나 하고 넘어가려고 한다.)

#include <iostream>
#define MAX 10001

using namespace std;

int a[MAX];
int d[MAX];

int getNext(int x) {
    int tmp=x, sum=x;
    while(tmp != 0) {
        sum += tmp%10;
        tmp /= 10;
    }
    return sum;
}

int main() {
    for(int i=1; i<MAX; i++) {
        for(int j=getNext(i); j<MAX; j=getNext(j)) {
            if(a[j]==1) continue;
            else a[j]=1;
        }
    }
    for(int i=1; i<MAX; i++) {
        if(a[i]==0) printf("%d\n", i);
    }

    return 0;
}