[백준 1929]-소수구하기(C++)

2022. 6. 9. 22:39· CodingTest/Baekjoon
목차
  1. 📕에라토스테네스의 체?
  2. 📗구현
  3. 👀오류

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 

3 16

예제 출력

3
5
7
11
13

 

💡이 문제는 에라토스테네스의 체를 활용하지 않으면 시간 초과가 나는 문제이다.

 

📕에라토스테네스의 체?

  • 간단하게 설명하면 2의 배수를 지우고, 3의 배수를 지우고 ,,, 이렇게 각자의 배수들을 지우는 것이다.
  • 이미 지워진 배수들은 넘어간다.
  • 대신 지우는 범위가 굉장히 중요하다.
  • 지우는 범위에 대한 설명은 아래 글로 대신한다.
1,2,3,5,6,10,15,30이 되겠지만 절반으로 나누었을때 √30이 정중앙에 올 것이다.
만약 √N보다 작은 범위에서 약수가 존재한다면 N은 소수가 아닐 것이다. 뒤에 √N보다 큰 범위는 조사할 필요가 없다. 약수는 딱 반으로 나눠서 있는지 없는지만 판단하면 되기 때문이다.

📗구현

  1. 2부터 N까지의 배열을 만들어서 일단 모두 소수가 아니라고 가정을 한다.
    1. 초기화를 1 로함.
  2. 2의 배수, 3의 배수, 5의 배수 ,,, √N의 배수까지 차례대로 지움.
    1. 지운다는 것은 초기화를 0으로 한다.
  3. M부터 N까지의 범위에서 값이 1인 것[소수인 것]을 찾아서 출력한다.

 

코드

/*
M과 N사이의 소수를 찾아내자.
에라토스테네스의 체 이용
2의 배수 제거. 3의배수 제거. 어디까지
루트 N까지 제거
루트 N이 절반 나눳을때 마지막 약수
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int M, N;
int main()
{
cin >> M >> N;
vector<int>include(N + 1);
for (int i = 2; i <= N; i++)
{
include[i] = 1;
}
include[1] = 0;
for (int i = 2; i<=sqrt(N); i++) //2부터 루트 N까지 검사함.
{
if (include[i] == 0) //만약 이미 소수가 아니라고 판별낫다면 검사할필요없음,
{
continue;
}
for (int j = i*i; j<=N;j=j+i) //i의 배수부터 N까지 배수를 싹 다지움.
{
include[j] = 0;
}
}
for (int i = M; i <= N; i++) //M부터 N까지의 소수를 출력하는데 소수는 include값이 1인것.
{
if (include[i] == 1)
{
cout << i<<"\n";
}
}
}

👀오류

나는 2부터 N까지만 1로 계산을 했는데 만약 M값이 1일 때를 생각을 안 해서 계속 오류가 났었다.

만약 오류가 난다면 1일 때의 경우의 수를 계산 안 해서 그럴 것이다.

 

저작자표시 (새창열림)

'CodingTest > Baekjoon' 카테고리의 다른 글

[백준 1057] 토너먼트(C++)  (0) 2022.06.26
[백준 16563] 어려운 소인수분해 구하기 (C++)  (0) 2022.06.10
[백준 7450] Bin Packing (C++)  (0) 2022.06.09
[C++] 백준 1978 - 소수 찾기  (0) 2022.06.01
[C++] 백준 1037 - 약수  (0) 2022.06.01
  1. 📕에라토스테네스의 체?
  2. 📗구현
  3. 👀오류
'CodingTest/Baekjoon' 카테고리의 다른 글
  • [백준 1057] 토너먼트(C++)
  • [백준 16563] 어려운 소인수분해 구하기 (C++)
  • [백준 7450] Bin Packing (C++)
  • [C++] 백준 1978 - 소수 찾기
재한
재한
안녕하세요 💻
재한
짜이한
전체
오늘
어제
  • 분류 전체보기 (504)
    • Skils (118)
      • Android (52)
      • C++ (5)
      • Kotlin (36)
      • Algorithm (24)
      • Server (1)
    • CodingTest (228)
      • Programmers (45)
      • Baekjoon (183)
    • Experience (8)
      • 후기(코딩테스트,프로그램,프로젝트) (8)
    • Computer Science (70)
      • Design Pattern (2)
      • OOP (2)
      • Computer Architecture (14)
      • OS (2)
      • Software Engineering (3)
      • DataBase (8)
      • Network (39)
    • 학교 (75)
      • R프로그래밍 (26)
      • 회계와 사회생활 (17)
      • 컴퓨터학개론 (20)
      • it기술경영개론 (12)

블로그 메뉴

  • 홈
  • 태그
  • 카테고리
  • 글쓰기
  • 설정

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
재한
[백준 1929]-소수구하기(C++)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.