기록 보관소

[Baekjoon/백준] 1929번: 소수 구하기(C/C++) 본문

코딩 테스트/백준

[Baekjoon/백준] 1929번: 소수 구하기(C/C++)

JongHoon 2022. 1. 20. 19:24

백준 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의 배수들)을 제거해 나가서 범위 내에 소수만 남게 만드는 것이다. 조금 더 이해하기 쉬운 설명은 아래 그림을 참고하면 좋을 것 같다.

출처 : https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

 


코드

#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; 을 넣지않아서 실패했었다..