백준 4948번 [c언어] : 소수 구하기

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

1929번: 소수 구하기

 

 

개쉽네 하고 이전 소수문제처럼 풀었다가 영혼까지 털렸다.

문제에 들어오기 전 백준 형님이 에라토스테네스의 체를 이용하여 풀라고 힌트를 주셨다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

고민을 하다가 계속 시간초과가 떠서 에라토스테네스의 체 공식을 보고 놀랐다..

나는 왜 이런생각을 하지 못했지...

 

○ 1은 소수가 아니므로 제외한다

 

○ 2는 소수이며 그 이후 2의 배수들은 소수가 아니다. 그러므로 배열에 2를 제외한 2의 배수들의

     배열  번호에 값 1을 주자

 

○ 3은 소수이며 그 이후 3의 배수들은 소수가 아니다. 그러므로 배열에 3을 제외한 3의 배수들의

    배열 번호에 값을 주자 

 

○ 4는 이미 2의 배열에서 값을 저장할 때 값이 주어졌으니 소수가 아니다. 4의 배수들의

     배열 번호에 값을 주자

 

○ 반복하면 소수만를 제외한 모든 숫자들 배열에 값이 들어있다. 소수 배열에는 값이 안들어가있다.

#include<stdio.h>

int main() {
	int a, b;
	int c[1000001] = {0};
	c[1] = 1;
	scanf("%d %d", &a, &b);

	for (int i = 2; i <= b; i++)
		for (int j = 2; j * i <= b; j++)
			c[i * j] = 1;
	
	for (int i = a; i <= b; i++)
		if (!c[i])
			printf("%d\n", i);
}