[ 정수론 - 소수 ] 알고리즘

 

1.  개념

 

알고리즘 문제에 자주 나오는 정수론 개념에는 '소수'와 '호제법'이 있다.

'소수' 관련 문제는 대부분 특정 범위 내에서 소수의 개수를 구하는 문제가 많이 출제된다.

 

[ 1 ]  소수

 

소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

 

n까지의 숫자 범위 내에서 소수를 찾는 방법 -> '에라토스테네스의 체'

 

< 에라토스테네스의 체 >

 

( 1 ) n만큼 일차원 리스트 생성

        * 리스트의 값을 인덱스 값으로 초기화

( 2 ) 리스트에서 지워지지 않았다면 리스트를 탐색하면서 현재 선택된 숫자의 배수를 삭제

        * 이때 현재 선택된 숫자는 삭제하지 않는다

( 3 ) 2에서부터 n의 제곱근까지 ( 2 )를 반복한 뒤 리스트에 남아있는 숫자를 출력

 

 

서로소 : 두 수의 공약수가 1 이외에 없는 관계

 

1~n과 서로소인 자연수의 개수를 각각 구하는 방법 -> 오일러 피 P(n)

 

< 오일러 피 >

 

( 1 ) n까지의 범위만큼 리스트 생성

       * 리스트의 값을 인덱스 값으로 초기화

( 2 ) 현재 리스트의 값과 인덱스가 같으면 현재 선택된 숫자의 배수에 해당하는 수(K)에 대해

         P(i) = P(i) - P(i) / K 를 수행

( 3 ) 2에서부터 리스트 끝까지 (2)를 반복

 

 

 

 

 

 

2. 문제 풀이

 

# 1  소수 구하기 - 백준 1929번

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

import sys
import math
input = sys.stdin.readline

m, n = map(int, input().split())
numlist = []

# 수의 범위만큼 리스트 생성
for i in range(n+1):
    numlist.append(i)

numlist[1] = 0

# 소수 구하는 방법_1
for i in range(2, int(math.sqrt(n))+1):  ##범위는 n의 제곱근까지
    if numlist[i] != 0:
        for j in range(i+1, n+1):
            if numlist[j] % i == 0:
                numlist[j] = 0

# 소수 구하는 방법_2
for i in range(2, int(math.sqrt(n)+1)):
	if numlist[i] != 0:
    	for j in range(i+i, len(numlist), i):  ## i(현재 선택한 수) 제외하고 i의 배수 제거
        	numlist[j] = 0

for i in range(m, n+1):
    if numlist[i] != 0:
        print(numlist[i])

 

 

* 처음에는 바깥 탐색 범위를 n/2 까지 했었는데 시간 초과가 나와서 탐색 범위를 n의 제곱근으로 낮추니까 풀렸다.

 

바깥 탐색 범위를 n의 제곱근까지만 해도 괜찮은 이유!

바깥 탐색 범위를 X라고 하면 전체 리스트에서 2부터 X의 배수들만 삭제한다는 뜻이다.

A = B * C 라고 했을 때 ( B와 C의 배수 A  /  A는 X보다 작거나 같다  /  X = (X의 제곱근) * (X의 제곱근) )

B와 C는 항상 X의 제곱근보다 작다. 

 

 

 

 

 

# 2  거의 소수 구하기

https://www.acmicpc.net/problem/1456

1456번: 거의 소수

 

 

 

# 3  소수 & 팰린드롬 수 중에서 최솟값 찾기

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

import sys
import math
input = sys.stdin.readline

n = int(input())
numlist = [0]*1100001
k = n

for i in range(2, len(numlist)):
    numlist[i] = i

for i in range(2, int(math.sqrt(len(numlist)))+1):
    if numlist[i] == 0:
        continue
    for j in range(i+i, len(numlist), i):
        numlist[j] = 0


def Pal(i):
    i = list(str(i))
    if i == i[::-1]:
        return True
    else:
        return False


while True:
    a = numlist[k]
    if a != 0:
        if Pal(a):
            print(a)
            break
    k += 1

 

계속 IndexError 나서 열 받아서 질문 게시판 찾아보니까 소수 찾는 범위를 110만까지 늘리라길래 그렇게 했더니 풀렸다....ㅎ 왜징??

 

 

 

 

 

 

# 4  제곱이 아닌 수 찾기 - 백준 1016번

https://www.acmicpc.net/problem/1016

1016번: 제곱 ㄴㄴ 수

 

 

 

# 5  오일러 피 - 백준 11689번

https://www.acmicpc.net/problem/11689

11689번: GCD(n, k) = 1