[백준] 27365번 : 소수가 아닌 수 (C언어 / C99)

문제

이 대회의 운영진 중 한 명인 KSA 학생은 17시와 19시를 구별할 수 없다. 이는 당연하게도 17과 19가 모두 소수이기 때문일 것이다. 시간을 제대로 구별해서 KSA의 명예를 지키기 위해 정수 N을 입력받아서 소수가 아닌 N 이상의 정수를 아무거나 구해주자.

 

 

조건 및 입출력

1. 첫 번째 줄에 정수 N이 주어진다.

2. 정답이 여러 개 존재한다면 아무거나 출력해도 상관없다.

3. 1 <= N <= 10^9

 

 

# 풀이는 2개이다.

 

1번 솔루션: 코드 (C99)

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

int main(void)
{
	long long nums;
	scanf("%lld", &nums);
	
	if (nums==1 || nums == 2 || nums==3)
	{
		printf("4");
		exit(0);
	}
		
	else
	{
		for (long long i = nums; i < (long long)10e9; i++)
		{
			for (long long j = 2; j < (long long)(sqrt(nums) + 1); j++)
				if (i % j == 0)
				{
					printf("%lld", i);
					exit(0);
				}
		}
	}
}

 

 

2번 솔루션 : 코드 (C99)

#include <stdio.h>

main()
{
	printf("1000000000");
}

 

 

풀이 과정

1번 솔루션:

 

단순히 에라토스테네스의 채를 떠올려서 풀이해도 된다.

단, 파이썬에서 에라토스테네스의 채를 구현해서 실행하면 시간 초과가 된다.

(C가 빨라서 다행이 통과가 되긴 했다만...)

 

입력값으로 1~3의 정수가 주어지면 소수가 아닌 첫 번 째 정수는 4이므로, 4를 출력한다. 

그렇지 않을 경우 주어진 수 부터 시작해서 10^9까지 루프(i)를 돌리고, 그 안에 2부터 시작하는 루프(j)를 돌린다.

i%j==0이면 소수가 아니므로 그 수를 출력하면 된다.

 

소수가 아닌 수를 찾는 즉시 더 이상 프로그램이 돌아갈 이유가 없으므로 exit(0)으로 프로그램을 종료시킨다.

 

 

2번 솔루션:

 

정답을 맞추고 나서, 다른 사람들은 어떻게 풀었는지 확인 해보았다.

사람들은 참 똑똑한 것 같다는 생각을 했다.

 

문제에서, N이상의 수 중에서 소수가 아닌 정수 아무거나 출력해도 된다는 말이 있다.

 

그리고 N의 범위는 1부터 10^9까지이다.

N 이상의 수는 최소값은 1, 최댓값은 10^9이다.

1을 입력했을 때 1이상의 수, 10^9를 입력하면 10^9이상의 수 중에서 소수가 아닌 수 아무거나 출력하면 된다.

 

10^9는 소수가 아니다. 

결국 10^9를 출력하면 그만이다.

어떤 수를 입력해도 최댓값은 10^9이고, 10^9는 소수가 아니기 때문이다.

 

 

---

 

코드가 이상하거나, 이해되지 않는 부분이 있다면 댓글 남겨주세요! + 더 좋은 풀이 방법이 있다면 알려주세요 :)