글 읽기 - 반례 부탁드립니다

17710 2년 전 0

M~N 범위에서 에라토스테네스의 체와 제곱근 범위 나누기 방법을 사용하여 풀이하는 방법을 사용하였습니다.

예제도 잘 출력되고 다른 질문 글의 반례를 넣어도 모두 잘 출력되는데 어떤 부분에서 문제가 발생하는 것일까요? 알려주시면 감사하겠습니다.

#pragma waring<disable: 4996>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void)
{
	int M;
	int N;
	int isPrime;
	int* prime;

	scanf("%d", &M);
	getchar();
	scanf("%d", &N);

	prime = (int*)malloc(sizeof(int) * (N - M + 1));

	for (int i = M; i <= N; i++)
	{
		isPrime = i;

		//예외 처리
		if (isPrime == 1)
			prime[i - M] = 0;

		if (isPrime == 2 || isPrime == 3)
		{
			prime[i - M] = isPrime;

			for (int j = (i - M) + isPrime; j <= (N - M); j += isPrime)
			{
				prime[j] = 0;
			}
		}

		for (int j = 2; j <= (int)sqrt(isPrime); j++)
		{
			//소수가 아니라면
			if (prime[i - M] == 0)
				break;

			//1, 자신 이외의 약수가 존재한다면
			if (isPrime % j == 0)
			{
				prime[i - M] = 0;
				break;
			}

			//소수라면
			if (j == (int)sqrt(isPrime))
			{
				prime[i - M] = isPrime;

				for (int k = (i - M) + isPrime; k <= N - M; k += isPrime)
				{
					prime[k] = 0;
				}
			}
		}
	}


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

	return 0;
}

dldyddlwl 2년 전 1

아래에 있습니다.

// 자, 우선 짚고 넘어가야할 것은 동적할당된 배열의 초기값은 흔히 말하는 쓰레기값입니다. 뭔지 모르겠지만 뭔가 있는거죠.

// 따라서, prime배열의 값들을 모두 우리가 확실하게 알 수 있는 값으로 정해놔야 오류나 실수를 피할 수 있습니다. 
// => 동적할당 배열을 쓸 때는 반드시 초기화를 해서 실수를 막기!!! (이 문제뿐만 아니라 항상 습관을 들여듭시다!)

for(int i = 0; i< N-M+1 ; i++)
{
        prime[i] = 100;        // 꼭 100일 필요는 없지만 0이 아닌 값으로 확실히 초기화시켜 놔야 합니다.
}
// 초기화의 과정!






// 자 그렇다면 구체적으로 어디서 문제가 되는 지 봅시다. 한번 찾아볼까요?!
int main(void)
{
	prime = (int*)malloc(sizeof(int) * (N - M + 1));

	for (int i = M; i <= N; i++) // 자, 만약에 M이 5라고 해봅시다. (M이 5니까 1,2,3 예외처리는 넘어갑시다)
	{                        // isPrime = i이므로, isPrime은 5입니다.
		isPrime = i;            // 그럼 루트5는 2.xx니까 인트로 자르면 2가 나오겠죠?
                                // 아래 for루프를 들어가게 됩니다. 

		for (int j = 2; j <= (int)sqrt(isPrime); j++)
		{
            
            // 그런데, 여기까지 오는 과정 중에 저희가 한번이라도 prime의 값을 건드린 적이 있던가요??
            
			//그런데 바로 prime 배열에 접근 => 동적할당으로 쓰레기값이 들어가있음
			if (prime[i - M] == 0)    // 만약에 진짜로 소수인데도, 쓰레기값이 들어있는데, 하필 우연히 이 값이 0이라면?!! 
				break;
		}
	}

17710 2년 전 0

우선 친절한 답변 감사합니다!!

배열 초기값을 어떤걸로 하면 괜찮을지 몰라서 초기화 하지 않고 사용했는데 초기화하는 습관을 들여두도록 해야겠습니다. 감사합니다!

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

문제

문제

출처

ICPC

반례 부탁드립니다

17710 2년 전 0

dldyddlwl 2년 전 1

17710 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말