글 읽기 - 8% 부근에서 오답으로 나옵니다.

yjh1440 3년 전 0

M, N이 입력되면,

1~N까지 배열에 넣고,

배열 내 데이터의 소수 여부 판별후,

M이상 N이하의 소수들을 출력하도록 코딩하였습니다.

시간초과 문제를 겪고나서, 에라토스테네스의 체를 활용하여 다시 코딩한건데..

반례를 파악할수가 없어 질문드립니다.

#include <stdio.h>
#include <math.h>

int arr[1000000] = { 0, }; // 1~1000000 배열

int main() {

	int M = 0, N = 0;
	scanf("%d %d", &M, &N);

	for (int i = 0; i < N; i++) { // 1~N까지 순차대로 삽입

		arr[i] = i + 1;
		
	}

	arr[0] = 0; // 배열 중 1은 제외 (소수가 아니므로 0처리)
    
	for (int j = 1; (j+1) < floor(sqrt(N)); j++) { // 2부터 N의 제곱근 배수까지 계산 반복 

		int k = 0;

		if (arr[j] != 0) { // 아래 과정에서 이미 0이 된 배열은 계산 안함

			k = j;

			while (k<N) { // 소수 판별위해 N까지 배수 계산

				if (arr[k + 1] % arr[j] == 0) {
	
					arr[k + 1] = 0; // 소수가 아닐 경우 0 처리

				}

				k++;
			}

		}

	}
	
	for (int z = M; z <= N; z++) { 

		if (arr[z-1] != 0) { // 배열 내 0이 아닌 수 (소수) 출력 (M이상 N이하) 

			printf("%d\n", arr[z-1]);

		}
	}
	
	return 0;

}

nahwasa 3년 전 1

힌트 : 21라인이 틀렸습니다.

잘 모르시겠으면 다시 댓글 주세요!

yjh1440 3년 전 0

21번라인 j+1을 j로 바꾸니 제곱근 제대로 계산합니다. 감사합니다.

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

문제

문제

출처

ICPC

8% 부근에서 오답으로 나옵니다.

yjh1440 3년 전 0

nahwasa 3년 전 1

yjh1440 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말