글 읽기 - 1929번 시간초과 한번만 봐주세요ㅠㅠ(C)

whdqor00 4년 전 0

문제를 m~n사이에 수를 모두 배열에 넣은 다음에 다시 한번 그 배열에 대해 반복문을 돌리면서 소수가 아닌 수들을 판별해서 그 수들을 -1로 바꾼 다음에 최종적으로 -1로 바뀌지 않은 소수들만 출력하는 방식으로 풀었습니다. 그런데 계속 시간초과가 뜨네요...암만 코드를 수정해봐도 계속 떠서 질문 남겨봅니다.

#include <stdio.h>

int main(void)
{
	int m, n, a = 0;
	int arr[1000000];

	scanf("%d %d", &m, &n);

	for (int i = 0; i <= n - m; i++)
	{
		arr[i] = i + m;

		for (int j = 2; j < arr[i]; j++)
		{
			if (arr[i] % j == 0)
				arr[i] = -1;
		}
	}

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

	return 0;
}

domece 4년 전 1

이 문제의 분류는 에라토스테네스의 체 입니다. 해당하는 내용을 검색해보시면 작성자분의 풀이보다 빠르게 작동하는 풀이를 떠올릴 수 있을 거에요.

djm03178 4년 전 1

https://www.acmicpc.net/board/view/39203

whdqor00 4년 전 0

아 두 분 조언 덕분에 풀었습니다!! 그런데 제가 쓴 코드가 에라토스테네스의 체를 잘 구현한게 맞는지 확인하고 싶은데 혹시 코드에서 잘못된 부분 있거나 제가 잘못 이해한 부분이 있다고 생각되시면 댓글로 남겨주시면 안될까요??

그리고 비주얼 돌려보면 int arr[1000001]로 배열의 크기를 지정할시 입력을 받기 전에 혼자 종료가 되어버립니다. 혹시 이 부분에 대해서는 어떤거 땜에 그런거지도 알려주실수 있으신가요??

#include <stdio.h>

int main(void)
{
	int m, n;
	int arr[1000001];
	scanf_s("%d %d", &m, &n);
	
	for (int i = m; i <= n; i++)
	{
		arr[i] = 1;
	}

	if (m == 1)
		arr[1] = 0;

	for (int i = 2; i <= n; i++)
	{
		for (int j = 2 * i; j <= n; j += i)
		{
			arr[j] = 0;
		}
	}

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

djm03178 4년 전 0

https://copynull.tistory.com/40

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

문제

문제

출처

ICPC

1929번 시간초과 한번만 봐주세요ㅠㅠ(C)

whdqor00 4년 전 0

domece 4년 전 1

djm03178 4년 전 1

whdqor00 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말