일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- FastAPI
- system hacking
- pytorch
- llm을 활용 단어장 앱 개발일지
- ML
- rao
- MDP
- Stream
- study book
- PCA
- BAEKJOON
- fastapi를 사용한 파이썬 웹 개발
- MATLAB
- DART
- Kaggle
- bloc
- Widget
- 영상처리
- Computer Architecture
- Got
- BFS
- Algorithm
- 파이토치 트랜스포머를 활용한 자연어 처리와 컴퓨터비전 심층학습
- 백준
- C++
- BOF
- Image Processing
- Flutter
- Dreamhack
- ARM
- Today
- Total
Bull
[백준] 2581: 소수 (C++) 본문
https://www.acmicpc.net/problem/2581
2581번: 소수
M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.
www.acmicpc.net
요구사항
① 첫 째줄, 두 째줄에 시작하는 숫자(Min)와 끝나는 숫자(Max)를 적어준다.
② Min이상 Max이하의 숫자 중 소수들의 합과 최솟값을 구해준다.
③ 만약 소수가 없으면 -1을 출력한다.
주의사항
-
코드
#include <iostream>
#include <vector>
using namespace std;
int main() {
int min, max;
int sum = 0;
int prime_m;
cin >> min >> max;
// 에라토스테네스 체
vector<bool> prime(max + 1, true);
prime[0] = false;
prime[1] = false;
for (int i = 2; i <= max; i++) {
if (prime[i]) {
for (int j = i + i; j <= max; j += i) {
prime[j] = false;
}
}
}
// min 1개만 구하기
for (int i = min; i <= max; i++) {
if (prime[i]) {
prime_m = i;
min = i;
sum += prime_m;
break;
}
}
// sum 구하기
for (int i = min + 1; i <= max; i++) {
if (prime[i]) {
sum += i;
}
}
if (sum)
cout << sum << endl << prime_m;
else
cout << -1;
return 0;
}
1. 에라토스테네스의 체
// 에라토스테네스 체
vector<bool> prime(max + 1, true);
prime[0] = false;
prime[1] = false;
for (int i = 2; i <= max; i++) {
if (prime[i]) {
for (int j = i + i; j <= max; j += i) {
prime[j] = false;
}
}
}
에라토스테네의 체는 정해진 범위 내에서 소수를 구하는 방법 중 하나이다.
모든 자연수 중에서 1과 자기 자신만을 약수로 하는 수(소수)를 구하는 것은 다른 방식으로 1과 자기 자신을 제외한 그 수의 배수들을 모두 지우면 된다.
예를 들어, 숫자 2를 검사할 때 1과 2를 제외한 4,6,8.... 은 소수가 아니라고 판정할 수 있다.
차례대로 3,4,5,6의 자기 자신을 제외한 배수들을 범위 내에서 지워주면 된다.
vector를 이용해 숫자에 대해 소수인가 아닌가의 판별성을 부여해준다.
0은 자연수가 아니니 false 이고,
1은 소수가 아니니 false이다.
index는 0부터 이니 max+1을 부여해 자연수(index)의 범위는 1~max가 된다.
나머지 vector의 bool값은 위의 에라토스테네스 체 방식을 이용해 판별해준다.
2. 소수의 최소값 구하기
// min 1개만 구하기
for (int i = min; i <= max; i++) {
if (prime[i]) {
prime_m = i;
min = i;
sum += prime_m;
break;
}
}
우선적으로 처음 소수를 발견하면 break를 통해 반복문을 종료하고 다음 반복문을 실행하면된다.
주의할점은 다음 검사 숫자(i)를 1올려주어야 한다.
그리고 소수의 합을 구하는 sum 변수에 소수를 더해준다.
3. 모든 소수의 합
// sum 구하기
for (int i = min + 1; i <= max; i++) {
if (prime[i]) {
sum += i;
}
}
4. 출력
if (sum)
cout << sum << endl << prime_m;
else
cout << -1;
return 0;
만약 Min과 Max 사이에 소수가 없으면 sum은 0이 되니 조건과 같이 -1을 출력해준다.
'Algorithm > Baekjoon' 카테고리의 다른 글
[백준] 10830: 뱀과 사다리 게임 (C++) (0) | 2024.05.08 |
---|---|
[백준] 10830: 행렬 제곱 (C++) (0) | 2024.04.04 |
[백준] 1408: 24 (C++) (1) | 2024.01.28 |
[백준] 5565: 영수증 (C++) (0) | 2024.01.26 |
[백준] 10984: 내 학점을 구해줘 (C++) (1) | 2024.01.25 |