반응형

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/2023

 

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 첫번 째 자리 숫자는 소수여야 하므로 2, 3, 5, 7 밖에 들어가지 못합니다.

 

2. 다음 자리 숫자부터는 짝수가 들어가면 소수가 되지 못하므로 홀수만 넣어주고, 소수 판별을 통해 소수인지 체크해줍니다.

 

3. 백트래킹을 통해 반복하면서 소수라면 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<cmath>
 
using namespace std;
 
bool isPrime(int num){
    if(num<2) return false;
    for(int i=2; i*i<=num; i++){
        if(num%i == 0) return false;
    }
    return true;
}
 
void dfs(int first, int n){
    //자릿수(n)가 0이 되면 그 수 출력
    if(n==0) printf("%d\n", first);
    
    for(int i=1; i<10; i+=2){   //홀수만 더해주기
        int tmp = first*10 + i;
        if(isPrime(tmp)){
            dfs(tmp, n-1);
        }
    }
 
}
int main(void){
    int n;
    scanf("%d", &n);
 
    //맨 앞 자릿수가 prime number 이어야합니다
    int prime[4] = {2, 3, 5, 7};
    for(int i=0; i<4; i++){
        dfs(prime[i], n-1);
    }
    return 0;
}
 
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 20311번 - 화학 실험 (C++)  (0) 2023.04.21
[ 백준 ] 11562번 - 백양로 브레이크 (C++)  (0) 2023.04.20
[ 백준 ] 2602번 - 돌다리 건너기 (C++)  (0) 2023.04.18
[ 백준 ] 1507번 - 궁금한 민호 (C++)  (0) 2023.04.17
[ 백준 ] 2668번 - 숫자고르기 (C++)  (0) 2023.04.16
반응형

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

티스토리툴바