Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- todolist
- 다이나믹 프로그래밍
- 5월
- 게임 엔진 공부
- 2023년
- 수학
- C/C++
- 2022년
- 백준
- 4월
- 2025년
- 7월
- 프로그래머스
- c++
- 1월
- 골드메탈
- 유니티
- 자료 구조
- 코딩 테스트
- 2024년
- 기초
- 코딩 기초 트레이닝
- 3월
- 6월
- 개인 프로젝트
- 유니티 심화과정
- 2월
- 단계별로 풀어보기
- 입문
- 개인 프로젝트 - 런앤건
Archives
- Today
- Total
기록 보관소
[Baekjoon/백준] 1929번: 소수 구하기(C/C++) 본문
백준 1929번: 소수 구하기
단계별로 풀어보기 9단계(기본 수학 2) 4번 문제
https://www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
문제 설명
M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.
입력과 출력
입력: 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
출력: 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

접근 방법
이번 문제는 이전 소수 문제들과는 달리, 100만이라는 큰 숫자까지의 범위가 주어져서 이전 문제들처럼 단순히 for문을 2중으로 사용하고 나머지를 계산해서 진행하면 시간초과가 일어날 것이다. 따라서 에라스토테네스의 체를 활용해서 문제를 해결해야한다.
에라스토테네스의 체는 간단히 말해서 특정 숫자의 배수들(ex. 2를 제외한 4,6,8 같은 2의 배수들)을 제거해 나가서 범위 내에 소수만 남게 만드는 것이다. 조금 더 이해하기 쉬운 설명은 아래 그림을 참고하면 좋을 것 같다.

코드
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 1000001
int main() {
int N, M;
int *isPrime = (int *)malloc(sizeof(int) * MAX);
memset(isPrime, 1, MAX * sizeof(int));
scanf("%d %d", &M, &N);
isPrime[1] = 0; //1은 소수가 아님
for (int i = 2; i <= N; i++)
for (int j = 2; i*j <= N; j++) //배수 구하기
isPrime[i*j] = 0; //소수가 아님
for (int i = M; i <= N; i++)
if (isPrime[i])
printf("%d\n", i);
free(isPrime);
return 0;
}
결과

아쉽게도 첫 제출때 isPrime[1] = 0; 을 넣지않아서 실패했었다..
'코딩 테스트 > 백준' 카테고리의 다른 글
[Baekjoon/백준] 9020번: 골드바흐의 추측(C/C++) (0) | 2022.01.22 |
---|---|
[Baekjoon/백준] 4948번: 베르트랑 공준(C/C++) (0) | 2022.01.21 |
[Baekjoon/백준]단계별로 풀어보기 9단계: 기본 수학 2-1번~3번(C/C++) (0) | 2022.01.19 |
[BaekJoon/백준] 1011번: Fly me to the Alpha Centauri(C/C++) (0) | 2022.01.18 |
[Baekjoon/백준]단계별로 풀어보기 8단계: 기본 수학 1-1번~8번(C/C++) (0) | 2022.01.17 |