반응형

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

 

1990번: 소수인팰린드롬

151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 값이 10,000,000보다 큰 팰린드롬수는 없으므로 b = min(b, 10,000,000)을 통해 b를 갱신합니다.

 

2. a부터 b까지 for문을 통해 돌면서 팰린드롬 수인지 체크하고, 팰린드롬 수라면 소수인지 판정 후 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<string>
#include<algorithm>
 
using namespace std;
 
int a, b;
int prime[10000001];
 
bool check(int num)
{
    string temp = to_string(num);
    string temp2 = temp;
    reverse(temp.begin(), temp.end());
 
    if (temp != temp2) return false;
    return true;
}
 
bool isPrime(int num)
{
    for (int i = 2; i * i <= num; i++) {
        if (num % i == 0) return false;
    }
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> a >> b;
 
    b = min(b, 10000000);
 
    for (int i = a; i <= b; i++) {
        if (check(i)) {
            if (isPrime(i)) {
                cout << i << '\n';
            }
        }
    }
 
    cout << -1 << '\n';
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
[ 백준 ] 15243번 - Tiling (C++)  (0) 2023.07.18
반응형

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

 

1456번: 거의 소수

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

www.acmicpc.net

 

 

1. arr 배열을 만들어 각 소수 여부를 저장합니다.

 

2. 소수를 vector<ll> prime에 저장합니다.

 

3. for문을 통해 prime을 돌면서 거듭제곱을 해주고, 그 수가 A <= N <= B 라면 ans++를 해줍니다.  이때, 오버플로우가 날 수도 있어서 해당 값을 i로 나눈 나머지가 0일 때 조건을 추가해 줍니다.  

 

4. ans를 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<iostream>
#include<vector>
#define ll long long
 
using namespace std;
 
ll A, B;
int arr[10000001];
vector<ll> prime;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> A >> B;
 
    for (ll i = 2; i * i <=B; i++) {
        if (!arr[i]) {
            prime.push_back(i);
            for (int j = 2; i * j * i * j <= B; j++) {
                arr[i * j] = 1;
            }
        }
    }
 
    int ans = 0;
 
    for (ll i : prime) {
        if (!arr[i]) {
            ll temp = 1LL * i;
            while(1){
                temp *= 1LL * i;
                if (temp > B || temp % i != 0) break;
                if (temp < A) continue;
                ans++;
            }
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17298번 - 오큰수 (C++)  (0) 2023.07.08
[ 백준 ] 6198번 - 옥상 정원 꾸미기 (C++)  (0) 2023.07.07
[ 백준 ] 1038번 - 감소하는 수 (C++)  (0) 2023.07.05
[ 백준 ] 11402번 - 이항 계수 4 (C++)  (0) 2023.07.04
[ 백준 ] 11401번 - 이항 계수 3 (C++)  (0) 2023.07.02
반응형

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

 

1963번: 소수 경로

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. visited 배열을 만들어 각 네 자릿수의 방문 여부를 저장합니다.

 

2. 에라토스테네스의 체를 이용하여 네 자릿수 소수들을 check 배열에 모두 저장합니다.

 

3. bfs를 이용하여 각 자릿수를 1씩 바꾸어주면서 방문 여부를 판별하고, 방문하지 않았다면 소수 여부를 판별하여 소수라면 queue에 넣어줍니다.

 

4. A 수가 B수로 변환이 가능하다면 cnt를 출력하고, 그렇지 않다면 Impossible을 출력합니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<iostream>
#include<queue>
 
using namespace std;
 
int T, A, B;
int check[10000];
int visited[10000];
 
int bfs(int A, int B)
{
    fill(visited, visited + 10000, 0);
    queue<pair<int, int>> q;
 
    q.push({ A,0 });
    visited[A] = 1;
 
    while (!q.empty()) {
        const int cur = q.front().first;
        const int cnt = q.front().second;
        q.pop();
 
        if (cur == B) {
            return cnt;
        }
 
        int temp = cur % 1000;
 
        for (int i = 1; i <= 9; i++) {
            int next = temp + i * 1000;
            if (visited[next] != 1) {
                visited[next] = 1;
                if (check[next] == 0) {
                    q.push({ next, cnt + 1 });
                }
            }
        }
 
        temp = cur;
 
        for (int i = 1; i <= 9; i++) {
            temp += 100;
            if ((temp % 1000) / 100 == 0) temp -= 1000;
            if (visited[temp] != 1) {
                visited[temp] = 1;
                if (check[temp] == 0) {
                    q.push({ temp, cnt + 1 });
                }
            }
        }
 
        temp = cur;
 
        for (int i = 1; i <= 9; i++) {
            temp += 10;
            if ((temp % 100) / 10 == 0) temp -= 100;
            if (visited[temp] != 1) {
                visited[temp] = 1;
                if (check[temp] == 0) {
                    q.push({ temp, cnt + 1 });
                }
            }
        }
 
        temp = cur;
 
        for (int i = 1; i <= 9; i++) {
            temp += 1;
            if (temp % 10 == 0) temp -= 10;
            if (visited[temp] != 1) {
                visited[temp] = 1;
                if (check[temp] == 0) {
                    q.push({ temp, cnt + 1 });
                }
            }
        }
    }
 
    return -1;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int i = 2; i <= 5000; i++) {
        for (int j = 2; j <= 5000; j++) {
            if (i * j < 10000) {
                check[i * j] = 1;
            }
            else break;
        }
    }
    
    while (T--) {
        cin >> A >> B;
 
        int temp = bfs(A, B);
 
        if (temp != -1) {
            cout << temp << '\n';
        }
        else {
            cout << "Impossible\n";
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 12869번 - 뮤탈리스크 (C++)  (0) 2023.06.28
[ 백준 ] 1707번 - 이분 그래프 (C++)  (0) 2023.06.27
[ 백준 ] 5052번 - 전화번호 목록 (C++)  (0) 2023.06.25
[ 백준 ] 3649번 - 로봇 프로젝트 (C++)  (0) 2023.06.23
[ 백준 ] 14940번 - 쉬운 최단거리 (C++)  (0) 2023.06.22
반응형

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

 

1016번: 제곱 ㄴㄴ 수

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 최솟값과 최댓값을 입력받습니다.

 

2. 구해야 하는 수의 범위가 최대 1,000,000이기 때문에 arr [ 1000001 ] 배열을 만들어서 각 숫자의 제곱 ㄴㄴ 수 여부를 판별합니다.

 

3. 범위 내 수의 개수를 ans에 대입합니다.(Max - Min + 1)

 

4. i = 2부터 for문을 돌며 i * i <= Max까지 i를 증가시키면서 그 배수에 Min을 뺀 값 즉, arr [ i * i * j - Min ]을 1로 바꿔주고, ans에 1을 빼줍니다.

 

5. 위의 과정 4에서 시작하는 j값을 얻기 위해 Min / i * i를 통해 나온 몫의 값에 나머지가 없다면 0을 나머지가 있다면 1을 더해줍니다.

 

6. ans를 출력해줍니다.

 

[ 소스코드 ]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#define ll long long
 
using namespace std;
 
ll arr[1000001];
ll Min, Max;
int ans;
 
int main()
{
    scanf("%lld %lld", &Min, &Max);
    ans = Max - Min + 1;    //범위 내 모든 수의 개수
 
    for (ll i = 2; i * i <= Max; i++) {
        ll pow = i * i;        //제곱수
        ll cnt = Min / pow;    //범위 내 나누어 떨어지는 수의 최솟값
 
        if (Min % pow) cnt++;    //나누어 떨어지지 않으면 몫 + 1
 
        for (ll j = cnt; j*pow <= Max; j++) {
            if (arr[j * pow - Min] != 1) {
                arr[j * pow - Min] = 1;
                ans--;
            }
        }
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1600번 - 말이 되고픈 원숭이 (C++)  (0) 2022.12.09
[ 백준 ] 16393번 - Lost Map (C++)  (0) 2022.12.08
[ 백준 ] 6091번 - 핑크 플로이드 (C++)  (0) 2022.12.06
[ 백준 ] 5427번 - 불 (C++)  (0) 2022.12.05
[ 백준 ] 4179번 - 불! (C++)  (0) 2022.12.04

+ Recent posts

티스토리툴바