1336 : 소수와 함께 하는 여행 - 연습문제

연습문제1) 다음과 같이 0 이 입력될때 까지 데이터를 입력 받아서 큐에 입력 후 큐의 값을 출력하시오.

입력예)

1 2 3 4 5 6 7 8 8 10 0

출력예)

1 2 3 4 5 6 7 8 8 10

 

연습문제2) 다음과 같이 0 이 입력될때 까지 데이터를 입력 받아서 큐에 입력 하되 이미 입력된 값은 제외하고 큐의 값을 출력하시오.

입력예)

1 2 3 4 5 6 7 8 8 10 0

출력예)

1 2 3 4 5 6 7 8 10

 

 

연습문제3) 다음과 같이 0 이 입력될때 까지 데이터를 입력 받아서 소수만 큐에 입력 하되 이미 입력된 값은 제외하고 큐의 값을 출력하시오.

입력예)

1 2 3 4 5 6 7 3 3 2 2 8 8 10 0

출력예)

2 3 5 7 

 

 

연습문제 4) 11부터 출발해서 99까지의 수 중에서 1자리수만 다른 소수로 이동할때 마지막에 출력되는 소수와 그 소수까지 몇번째 만에 갔는지 출력하시오.

 

출력예)

89 3

힌트) 다음과 같은 경로로 큐에 들어가고 마지막에 89 3 이 출력 된다.

11 1
31 2
41 2
61 2
71 2
13 2
17 2
19 2
37 3
43 3
47 3
67 3
73 3
79 3
23 3
53 3
83 3
97 3
29 3
59 3
89 3

 

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;

struct data{
    int a,seq;
};

queue <struct data> q;

int prime[1010]={1,1};
int visit[1010];
void eratos()
{
    for(int i=2;i<=1000;i++)
    {
        if(prime[i]) continue;
        for(int j=i*i;j<=1000;j+=i) prime[j]=1;
    }
}

void push_q(struct data a)
{
    if(prime[a.a]) return ;
    if(visit[a.a]) return;
    visit[a.a]=1;
    q.push(a);
}


int main()
{
    eratos();
    push_q({11,1}); ///처음 출발 하자.

    while(!q.empty()){
        data imsi = q.front();
        cout << imsi.a << " " << imsi.seq << endl;
        q.pop();
        for(int j=1;j<=9;j++) ///첫번째 자리를 1 부터 9까지 바꿔 보자.
        {
            push_q({j*10 + imsi.a % 10,imsi.seq+1});
        }
        for(int j=0;j<=9;j++) ///두 번째 자리를 0 부터 9까지 바꿔 보자.
        {
            push_q({imsi.a / 10 * 10 + j,imsi.seq+1});
        }
    }

    return 0;
}

 

연습문제 5) 101부터 출발해서 999까지의 수 중에서 1자리수만 다른 소수로 이동할때 마지막에 출력되는 소수와 그 소수까지 몇번째 만에 갔는지 출력하시오.

 

출력예)

953 6

 

연습문제 6) 1009부터 출발해서 9999까지의 수 중에서 1자리수만 다른 소수로 이동할때 마지막에 출력되는 소수와 그 소수까지 몇번째 만에 갔는지 출력하시오.

 

출력예)

6983 7