Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- CS
- Kotlin
- 스택
- 구현
- 시뮬레이션
- java
- JUnit 5
- 플로이드-와샬
- 문자열
- 투 포인터
- 유니온 파인드
- 위상정렬
- 이분탐색
- 프로그래머스
- 후니의 쉽게 쓴 시스코 네트워킹
- 알고리즘
- dfs
- 동적계획법
- 그리디
- 완전탐색
- 세그먼트 트리
- Network
- mst
- 백준
- Effective Java
- 백트래킹
- 수학
- swea
- BFS
- 에라토스테네스의 체
Archives
반갑습니다!
[백준] 2153 소수 단어 본문
풀이
에라토스테네스의 체를 사용해 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 |