[백준 / BOJ] 1929번 소수 구하기 (C++, Python)

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

1929번: 소수 구하기

---

문제

---

문제 풀이

이전에 포스팅했던 소수 찾기, 소수 문제들과 같은 맥락이다. 출력값만 조금 조정해주면 된다.

 

 

C++ 코드 전문

	#include <iostream>
	#include <cmath>
	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() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int M, N;
	cin >> M >> N;
	for (int i = M; i <= N; ++i) {
	if (isPrime(i))
	cout << i << "\n";
	}
	return 0;
	}

view raw 1929_소수 구하기 (22.04.06 성공).cpp hosted with ❤ by GitHub

 

Python 코드 전문

	M, N = map(int, input().split())
	arr = [False, False] + [True] * (N - 1)
	i = 2
	# 에라토스테네스의 체
	while i <= N:
	if arr[i]: # 지워나가는 과정
	for j in range(i + i, N + 1, i):
	if arr[j]:
	arr[j] = False
	i += 1
	for i in range(M, N + 1):
	if arr[i]:
	print(i)

view raw 1929_소수 구하기 (22.04.06 성공).py hosted with ❤ by GitHub

 

소감