백준(C언어)/22년 8월

8월 9일(화) - 8단계(1929번)

C0MPAS 2022. 8. 9. 22:36

8단계 - 1929번https://www.acmicpc.net/problem/1929

 

1929번: 소수 구하기

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

www.acmicpc.net

 

문제점

1. 검색해보니 에라토스테네스의 체 라는 방법을 활용한 코드작성이 가장 유용하다는 것을 알게되었다

-> 출처의 코드를 많이 참고했기 때문에, 추가적인 공부가 필요한 상황

 

풀이 - 1 (에라토스테네스의 체)

출처: https://velog.io/@usoab0561/%EB%B0%B1%EC%A4%80-1929%EB%B2%88-%EC%86%8C%EC%88%98%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%84%B1%EA%B3%B5

#include <stdio.h>
int main(void){
    int m,n,arr[1000001] = {0,};
    arr[1] = 1;
    
    scanf("%d %d", &m, &n);
    
    for(int i = 2; i <= n; i++){
        for(int j = 2; i * j <= n; j++){
            arr[i*j] = 1;
        }
    }
    
    for(int i = m; i <= n; i++){
        if(arr[i] == 0)
            printf("%d\n",i);
    }
    
    return 0;
}

 

 

풀이 - 2 (최소시간)

출처: https://detective.tistory.com/14

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int arr[1000001];

int main() {
	int m, n;
	int i, j;
	scanf("%d %d", &m, &n);

	for (i = 2; i <= n; i++) {
		if (!arr[i]) {
			for (j = i + i; j <= n; j += i)
				arr[j] = 1;
		}
		if (i >= m && arr[i] == 0) printf("%d\n", i);
	}

	return 0;
}

 

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