반갑습니다!

[백준] 2153 소수 단어 본문

알고리즘 문제 풀이

[백준] 2153 소수 단어

김덜덜이 2020. 10. 5. 22:00

풀이

에라토스테네스의 체를 사용해 1부터 최대값인 20 * 52 까지의 범위에 있는 소수를 모두 구한 뒤, 입력 들어온 문자열을 숫자로 바꿔서 소수 여부를 확인했다.

코드

C++

#include <iostream>
using namespace std;

const int MAX = 20 * 52;

int main() {
    bool arr[MAX + 1];
    for (int i = 1; i <= MAX; i++) arr[i] = true;

    for (int i = 2; i * i <= MAX; i++) {
        if (arr[i]) {
            int j = 2;
            while (i * j <= MAX) {
                arr[i * j] = false;
                j++;
            }
        }
    }

    string s;
    int sum = 0;
    cin >> s;
    for (char c : s) {
        if ('a' <= c && c <= 'z') sum += (c - 'a' + 1);
        else sum += (c - 'A' + 27);
    }
    if (arr[sum]) cout << "It is a prime word.\n";
    else cout << "It is not a prime word.\n";
    return 0;
}

Python3

import math

MAX = 20 * 52

array = [True for _ in range(MAX + 1)]

for i in range(2, int(math.sqrt(MAX)) + 1):
    if array[i]:
        j = 2
        while i * j <= MAX:
            array[i * j] = False
            j += 1
s = input()
sum = 0

for i in range(len(s)):
    if 'a' <= s[i] <= 'z':
        sum += (ord(s[i]) - ord('a')) + 1
    else:
        sum += (ord(s[i]) - ord('A') + 27)
if array[sum]:
    print('It is a prime word.')
else:
    print('It is not a prime word.')

'알고리즘 문제 풀이' 카테고리의 다른 글

[백준] 1647 도시 분할 계획  (0) 2020.10.06
[백준] 15809 전국시대  (0) 2020.10.06
[백준] 3986 좋은 단어  (0) 2020.10.05
[백준] 2096 내려가기  (0) 2020.10.04
[백준] 11060 점프 점프  (0) 2020.10.04