📝1978번: 소수 찾기
N개의 수 중에서 소수가 몇 개인지 찾는 문제
소스코드 중간에1) j < num이 아니라2) j * j <= num인 이유는
1) 시간복잡도: O(n)인 반면,2) 시간복잡도: O(root n)라서
효율적이기 때문이다
라피신 C05 과제가 도움이 되었다
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
int N; // 주어진 수의 개수
int num;
int cnt = 0; // 소수의 개수
cin >> N;
for (int i = 0; i < N; i++){
cin >> num;
int prime = 0;
for(int j = 2; j * j <= num; j++){
if (num % j == 0)
prime++;
}
if (prime == 0 && num != 1)
cnt++;
}
cout << cnt;
return 0;
}📝2581번: 소수
M부터 N까지의 자연수 범위에서 소수들의 합을 구하고 소수 중 최솟값을 찾는 문제
한번 틀렸는데 이유는is_prime 함수에서 1을 처리하지 않았기 때문이다
1은 소수가 아니지.. 주어진 test case만 믿고 제출하면 안된다
exceptional case를 생각하자
❓의문: 두 번의 while문 사용으로 min++를 했을 때 다음 while문에
증가된 min이 적용이 왜 안되는가? 그거 때문에 일부러 새로운 변수 m을 선언했는데
변수의 scope와 lifespan에 대해서 다시 공부하자
❗해결: 어차피 소수 중 최솟값부터 다음 while문 시작이기 때문에
다음 while문에 들어가서도 제대로 된 값이 나올 수 있었던 것
즉 내가 알던 것이 맞다. 다음 while문에 증가된 min이 적용되는 것
💻소스코드
#include <iostream>
using namespace std;
bool is_prime(int n){ // 소수 판별 함수
if (n == 1)
return 0;
for(int i = 2; i * i <= n; i++){
if (n % i == 0)
return 0;
}
return 1;
}
int main(void) {
int min, max, m;
int min_prime;
int prime_sum = 0;
int cnt = 0; // 소수의 갯수 카운트
cin >> min >> max;
m = min;
while (m <= max){ // 소수 중 최솟값
if (is_prime(m)){
min_prime = m;
break;
}
m++;
}
while (min <= max){ // 소수 합
if (is_prime(min)){
cnt++;
prime_sum += min;
}
min++;
}
if (cnt == 0) // 소수가 없을 때
cout << "-1\n";
else
{
cout << prime_sum << "\n";
cout << min_prime;
}
return 0;
}📝11653번: 소인수분해
자연수 N의 소인수분해 결과를 오름차순으로 출력하는 문제
N이 1일 땐 아무것도 출력하지 않는다
N을 i로 나눈 나머지가 0이고 i를 증가시키면서 반복하면 끝
💻소스코드
#include <iostream>
using namespace std;
int main(void) {
int N;
cin >> N;
int i = 2;
while (N > 0){
if (N == 1)
break;
if (N % i == 0){
N /= i;
cout << i << "\n";
i--;
}
i++;
}
return 0;
}📝1929번: 소수 구하기
자연수 M과 N사이의 모든 소수를 구하면 되는 문제
is_prime 함수구현하고 한줄씩 출력해주면 끝
💻소스코드
#include <iostream>
using namespace std;
bool is_prime(int n){
if (n == 1)
return false;
for(int i = 2; i * i <= n; i++){
if (n % i == 0)
return false;
}
return true;
}
int main(void) {
int M, N;
cin >> M >> N;
while (M <= N){
if (is_prime(M))
cout << M << "\n";
M++;
}
return 0;
}📝4948번: 베르트랑 공준
n보다 크고 2n보다 작거나 같은 자연수에는 소수가 적어도 하나 이상 존재하니까
그 사이 소수의 갯수를 출력하라는 문제
💻소스코드
#include <iostream>
using namespace std;
bool is_prime(int n){
if (n == 1)
return false;
for(int i = 2; i * i <= n; i++){
if (n % i == 0)
return false;
}
return true;
}
int main(void) {
int n;
while (true){
cin >> n;
if (n == 0)
break;
int cnt = 0; // 소수의 갯수
for(int i = n + 1; i <= 2 * n; i++){
if (is_prime(i))
cnt++;
}
cout << cnt << "\n";
}
return 0;
}📝9020번: 골드바흐의 추측
짝수를 가장 차이가 적은 두 소수의 합으로 나타낸 골드바흐 파티션을 출력하는 문제
두 소수의 차이가 가장 작아야 하므로 n을 입력받자마자 2로 나눠서 a, b에 각각 저장
a, b가 각각 소수이면 차례대로 출력하고, 아니면 a는 1씩 줄이고 b는 1씩 늘려주면 끝
💻소스코드
#include <iostream>
using namespace std;
bool is_prime(int n){
if (n == 1)
return false;
for(int i = 2; i * i <= n; i++){
if (n % i == 0)
return false;
}
return true;
}
int main(void) {
int test;
int n;
int a, b;
cin >> test;
for(int i = 0; i < test; i++){
cin >> n; // 4 <= n <= 10,000
a = n/2;
b = n/2; // 두 소수의 차이가 가장 작게
while (a >= 2){
if (is_prime(a) && is_prime(b)){
cout << a << " " << b << "\n";
break;
}
a--; // 하나씩 줄여가면서
b++; // 하나씩 늘려가면서
}
}
return 0;
}BOJ "기본수학 2" 단계를 통해서 소수와 관련된 문제들을 풀어봤다
이전에도 소수 관련 문제들을 접해봤어서 그런지 다소 난해하거나 어렵게 느껴지지 않았다
