[백준 / BOJ] 2581번 소수 (C++, Python)

링크 : https://www.acmicpc.net/problem/2581

2581번: 소수

---

문제

---

문제 풀이

바로 전 문제인 소수 찾기와 같은 알고리즘을 사용한다. 조건만 추가되었을 뿐이다.

 

 

C++ 코드 전문

	#include <cmath>
	#include <iostream>
	using namespace std;
	// 원래는 루프를 2부터 나누어 n-1까지의 수 중 나머지가 0이 되는 수가 존재하는지
	// 판별해야 함. 하지만 너무 비효율적이기 때문에 루프 횟수를 줄여야 함.
	// 제곱근까지만 반복해도 가능하다고 알려져 있음.
	bool isPrime(int val) {
	if (val < 2)
	return false;
	else {
	for (int i = 2; i <= sqrt(val); ++i) {
	if (val % i == 0) return false;
	}
	}
	return true;
	}
	int main() {
	int M, N, check = 0, res = 0, min;
	cin >> M >> N;
	for (int i = M; i <= N; ++i) {
	if (isPrime(i)) {
	res += i;
	if (check == 0) { // 최솟값을 저장하기 위함
	min = i;
	check++;
	}
	}
	}
	if (check == 0) // 소수가 아예 존재하지 않음
	cout << -1 << "\n";
	else
	cout << res << "\n" << min << "\n";
	}

view raw 2581_소수 (22.04.06 성공).cpp hosted with ❤ by GitHub

 

Python 코드 전문

	M = int(input())
	N = int(input())
	arr = [False, False] + [True] * 9999
	i = 2
	# 에라토스테네스의 체
	while i <= 10000:
	if arr[i]: # 지워나가는 과정
	for j in range(i + i, 10001, i):
	if arr[j]:
	arr[j] = False
	i += 1
	res = 0
	check = 0
	min = 0
	for i in range(M, N + 1):
	if arr[i]:
	res += i
	if check == 0:
	min = i
	check = 1
	if check == 0:
	print("-1")
	else:
	print(f"{res}\n{min}")

view raw 2581_소수 (22.04.06 성공).py hosted with ❤ by GitHub

 

소감