글 읽기 - [C언어] 예제는 정상적으로 출력되지만 시간 초과라고 뜹니다.

hyunbinny 2년 전 0

아무래도 이중 For문을 사용한 것 때문에 시간 초과가 일어나는 것 같은데 이 부분을 어떻게 손봐야 할 지 감이 안 잡히네요..

#include <stdio.h>

int main(void)
{
	int m, n;
	int arr[10000] = {0,};

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

g072923 2년 전 0

이 문제는 에라토스테네스의 체를 사용해야하는 문제입니다.

에라토스테네스의 체를 한번 검색해보세요

fccva 2년 전 0

n이 소수인지 아닌지 판단하기 위해서 n-1까지 나눠볼 필요가 없습니다!

hyunbinny 2년 전 0

12번째 줄 for문의 조건식을 아래와 같이 sqrt(i)까지만 확인하는 것으로 바꾼 후에 다시 채첨해본 결과 89%에서 틀렸다고 나옵니다..

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

fccva 2년 전 0

49를 판단하려면 7까진 확인을 해야겠죠?

j * j <= i 로 바꿔보세요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C언어] 예제는 정상적으로 출력되지만 시간 초과라고 뜹니다.

hyunbinny 2년 전 0

g072923 2년 전 0

fccva 2년 전 0

hyunbinny 2년 전 0

fccva 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말