[Python] 4134. 다음 소수

문제

정수 n(0 ≤ n ≤ 4*109)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다.

출력

각각의 테스트 케이스에 대해서 n보다 크거나 같은 소수 중 가장 작은 소수를 한 줄에 하나씩 출력한다.

예제 입력 1

3
6
20
100

예제 출력 1

7
23
101

---

소수를 구하는 방법이 무엇이 있는 지에 대해 찾아보았다. 그 중 고대 그리스의 수학자 에라토스테네스가 만들어 낸 방법인 '에라토스테네스의 체'라는 방법을 찾아 해법에 적용시켜보았다. 

'에라토스테네스의 체'는 특정 범위 안에 있는 소수를 찾는 방법으로 아주 유용한 방법인데, 이를 예시로 들어 1 ~ 144 까지 숫자 중 소수를 찾는다고 하면, 아래와 같은 순서로 이루어진다.

일단 1부터 144까지 숫자를 쭉 쓴다.

 

1	2	3	4	5	6	7	8	9	10	11	12
13	14	15	16	17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32	33	34	35	36
37	38	39	40	41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70	71	72
73	74	75	76	77	78	79	80	81	82	83	84
85	86	87	88	89	90	91	92	93	94	95	96
97	98	99	100	101	102	103	104	105	106	107	108
109	110	111	112	113	114	115	116	117	118	119	120
121	122	123	124	125	126	127	128	129	130	131	132
133	134	135	136	137	138	139	140	141	142	143	144

일단 소수도, 합성수도 아닌 유일한 자연수 1을 제거하자.

1	2	3	4	5	6	7	8	9	10	11	12
13	14	15	16	17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32	33	34	35	36
37	38	39	40	41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70	71	72
73	74	75	76	77	78	79	80	81	82	83	84
85	86	87	88	89	90	91	92	93	94	95	96
97	98	99	100	101	102	103	104	105	106	107	108
109	110	111	112	113	114	115	116	117	118	119	120
121	122	123	124	125	126	127	128	129	130	131	132
133	134	135	136	137	138	139	140	141	142	143	144

2를 제외한 2의 배수를 제거한다.

	2	3	4	5	6	7	8	9	10	11	12
13	14	15	16	17	18	19	20	21	22	23	24
25	26	27	28	29	30	31	32	33	34	35	36
37	38	39	40	41	42	43	44	45	46	47	48
49	50	51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70	71	72
73	74	75	76	77	78	79	80	81	82	83	84
85	86	87	88	89	90	91	92	93	94	95	96
97	98	99	100	101	102	103	104	105	106	107	108
109	110	111	112	113	114	115	116	117	118	119	120
121	122	123	124	125	126	127	128	129	130	131	132
133	134	135	136	137	138	139	140	141	142	143	144

3을 제외한 3의 배수를 제거한다.

	2	3		5		7		9		11
13		15		17		19		21		23
25		27		29		31		33		35
37		39		41		43		45		47
49		51		53		55		57		59
61		63		65		67		69		71
73		75		77		79		81		83
85		87		89		91		93		95
97		99		101		103		105		107
109		111		113		115		117		119
121		123		125		127		129		131
133		135		137		139		141		143

 

4의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.)
그러면 2, 3 다음으로 남아있는 가장 작은 소수, 즉 5를 제외한 5의 배수를 제거해야 한다.

	2	3		5		7				11
13				17		19				23
25				29		31				35
37				41		43				47
49				53		55				59
61				65		67				71
73				77		79				83
85				89		91				95
97				101		103				107
109				113		115				119
121				125		127				131
133				137		139				143

6의 배수는 지울 필요 없으니(2의 배수에서 이미 지워졌다.) 7을 제외한 7의 배수를 제거한다.

	2	3		5		7				11
13				17		19				23
				29		31
37				41		43				47
49				53						59
61						67				71
73				77		79				83
				89		91
97				101		103				107
109				113						119
121						127				131
133				137		139				143

8의 배수는 지울 필요 없다.(2의 배수에서 이미 지워졌다.) 9의 배수도 지울 필요 없다.(3의 배수에서 이미 지워졌다.) 10의 배수도 지울 필요 없다.(2의 배수에서 이미 지워졌다.) 마지막으로 11을 제외한의 11의 배수 중 121과 143을 제거하면 다음과 같이 된다.

	2	3		5		7				11
13				17		19				23
				29		31
37				41		43				47
				53						59
61						67				71
73						79				83
				89
97				101		103				107
109				113
						127				131
				137		139

이런 식으로 특정 수까지 소수를 찾을 때 가장 작은 소수의 배수부터 제거하는 방식으로 소수를 찾는 방법을 '에라토스테네스의 체'라 한다.

 

이제 이 방법을 문제에 적용시켜보자, 문제에선 주어진 숫자가 소수면 주어진 숫자를, 아니라면 주어진 숫자보다 크면서 가장 근접한 소수를 구하라 나와있다. 이를 위해서는 먼저, 주어진 숫자가 소수인지 판별하고 아니라면 숫자를 1 씩 증가시켜 판별하는 방식으로 접근했다.

 

1. 먼저 주어진 숫자가 소수인지 판별하는 함수를 생성한다.

def check(n):
	nums = int(n ** 0.5) + 1		# ** 은 거듭제곱을 의미 즉, ** 0.5 = 루트를 의미한다.
    for num in range(2, nums):
    	if n % num == 0:
        	return False
    return True

 

1 을 제외한 모든 양의 정수에서 2 부터 해당 양의 정수의 거듭제곱근까지 나눈 값의 나머지가 0이 아닐 경우에는 그 수는 소수로 판별한다.

예를 들어, 23 이라는 숫자를 저 함수에 대입하면,

nums = int(23 ** 0.5) + 1 = 루트 16과 루트 25 사이의 수 이기 때문에 4.xxx 이나 int형으로 하여 4 + 1 = 5

23 % 2 = 3 | 23 % 3 = 2 | 23 % 4 = 3

이므로, 23은 소수이다. 5 이상의 숫자를 비교하지 않는 이유는 '에라토스테네스의 체'의 성질에 입각한 이유로, 루트 n 보다 작은 수의 배수만 체크해도 전부 지워진다는 성질 때문이다. (루트 23이 4.xxx)

 

2. 나머지 조건을 넣은 반복문을 통해 주어진 숫자가 소수인 지 아니라면, 1 을 증가시켜 재 판별시킨다.

최종 코드

import sys

T = int(sys.stdin.readline())

def check(n):
    nums = int(n ** 0.5) + 1
    for num in range(2, nums):
        if n % num == 0:
            return False
    return True

for _ in range(T):
    n = int(sys.stdin.readline())
    while True:
        if n == 0 or n == 1:
            print(2)
            break
        else:
            if check(n):
                print(n)
                break
            else:
                n += 1