🧚‍♂️알고리즘🧚‍♂️ - 정수론1(소수,오일러 피)

🌊정수론 - 수의 성질을 탐구하고 공부하는 분야 🌊

---

🔢소수 구하기🔢

소수:

자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수.

(1과 자기 자신 외에 약수가 존재하지 않는 수)

 

소수 구하기의 핵심 이론 

에라토스테네스의 체

1. 구하고자 하는 소수의 범위만큼 1차원 리스트 생성

2. 2부터 시작하여 지워지지 않은 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다.

3. 리스트의 끝까지 2번을 반복한 후 리스트에 남아 있는 수를 출력한다.

 

에라토스테네스의 체 시간복잡도

O(N^2) 같겠지만 일반적으로 O(Nlog(logN))이라고 한다.

왠지 이해가 안 돼서 검색해봤더니

Sieve of Eratosthenes - Wikipedia

그렇구나 하고 넘어가야 하는 것들이 가끔 있는 법이다

---

🥈실버3

1929번: 소수 구하기

import math
from sys import stdin
M,N = map(int,stdin.readline().split())

Nlist = [0] * (N+1)

# 1번 
for i in range(2,N+1):
    Nlist[i] = i

#2번 
#N의 제곱근까지만 보는 이유: 그 이후~N까지의 수의 약수는, 둘 중 하나는 무조건 M의 제곱근이게 된다. 따라서 이전에 이미 사라졌을 것이다.
for i in range(2,int(math.sqrt(N))+1) :
    if Nlist[i] != 0 :
        for j in range(i*2,N+1,i):
            Nlist[j] = 0

#3번
for i in range(M,N+1):
    if  Nlist[i] != 0:
        print(i)

+ math.sqrt(x) 함수

x의 제곱근을 반환(float형)

 

+N의 제곱근까지만 보는 이유: !

그 이후~N까지의 수의 약수는, 둘 중 하나는 무조건 M의 제곱근이게 된다. 따라서 이전에 이미 사라졌을 것이다.

---

🥈실버 1

1456번: 거의 소수

import math
from sys import stdin
A, B = map(int,stdin.readline().split())
len = 1000_0000+1
Nlist = [0] * (len)

# 최소 2제곱이므로 소수는 10^7까지만 구하면 됨 
for i in range(2,len):
    Nlist[i] = i

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

result = 0
for i in range(2,len):
    if  Nlist[i] != 0:#소수들 중에서
        n = i * !
        '''
        while(n <= B):
            if n >= A:
                result+=1
            n *= i
        '''
        while(i <= B/n):
            if i >= A/n:
                result+=1
            n *= i

print(result)

---

🥇골드 5

1747번: 소수&팰린드롬

- 모든 소수를 에라토스테네스의 체를 통해 구한 후 N보다 크거나 같은 소수들 보기

(N보다 큰 소수만 구하면 안 되나? 안됨. 에라토스테네스의 체 원리가 처음부터해야하는거임)

 

풀이

- 2~ 10000000사이에 존재하는 모든 소수를 구한다

- N보다 크거나 같은 소수부터 팰린드롬 수인지를 확인한다.

 

팰린드롬 수 확인 방법

- 소수를 리스트 형태로 변경한 후 투 포인터를 이용해 검사

import math
from sys import stdin

N = int(stdin.readline())
Nlist = []

# 소수리스트 기본세팅 (2_10_000_000)
for i in range(10_000_001):
    Nlist.append(i)

Nlist[1] = 0 # 1반례 처리
# 소수들 구하기
for i in range(2,  int(math.sqrt(10_000_000))+1):
    if Nlist[i] != 0:
        for j in range(i*2 , 10_000_001, i):
            Nlist[j] = 0

#소수들 순서대로 팰린드롬 수인지 판별하기
n = N
notFound = True
while(notFound):
    if Nlist[n] != 0:
        palin = str(Nlist[n])
        s = 0
        l = len(palin)-1
        while(s <= l): # = 없으면 한 자리 수 통과 안됨!!
            if palin[s] == palin[l]:
                s += 1
                l -= 1
                notFound = False
            else:
                notFound = True
                break
    n += 1
        
print(n-1)

틀렸다!

 

아하~ 

while(s < l):에 = 가 없어서 1자리 수가 팰린드롬으로 통과가 안 된다

 

아하~

잘 가다가 갑자기 틀렸습니다가 뜨면 극단적인 테케를 빼먹었을 가능성이 크다. 

1 처리를 안해줬었다. 

Nlist[1] = 0를 추가하면

 

맞았습니다!

---

🥇골드 1

1016번: 제곱 ㄴㄴ 수

제곱수를 찾기 위해 그냥 반복문 사용하면 시간초과!

=> 에라토스테네스의 체 로직 변형하기

 

max까지의 범위 이용하면 메모리 초과!

=> min- max 사이 범위만 이용하기

import math
from sys import stdin

min, max = map(int,stdin.readline().split())
twoNum = [False] * (max-min+1)
result = max - min + 1

for i in range(2, int(math.sqrt(max))+1): #제곱수 찾는 거니까 제곱근까지만
    num = i ** 2
    #제곱수의 배수들 보기.
    # min이상의 가장 작은 num의 배수부터,
    if (min % num == 0):
        start = min // num
    else: # => min이 num으로 딱 나누어 떨어지지 않을 시 수가 작아지는 것 보정
        start = min // num + 1

    for j in range(start*num , max+1, num):
        if not twoNum[j-min]:
            twoNum[j-min] = True
            result -= 1 # 전체 범위에서 아닌 것 빼기 

print(result)

으악 어려워 진짜

---

🔢오일러 피🔢

 

🩸오일러 피 함수

P[N] = 1부터 N까지의 범위에서 N과 서로소인 자연수의 개수

구하는 법
1️⃣ 구하고자 하는 오일러 피의 범위만큼 , 리스트를 자신의 인덱스값으로 초기화
2️⃣ 2부터 시작하여 / 현재 리스트의 값 == 인덱스의 값(변경되지 않았음)일 시 / 현재 선택된 수(K)의 배수에 해당하는 수를 리스트 끝까지 탐색하며 P[i] = P[i] -  P[i]/K 연산을 수행
3️⃣ 리스트의 끝까지 2️⃣을 반복하여 오일러 피 함수를 완성

증명은 패스~

---

 

🥇골드 1

11689번: GCD(n, k) = 1

🩸GCD는 최대공약수라는 뜻이다.

 

GCD(n,k) = 1 이라는 말은 즉

n 과 k 가 서로소라는 뜻이므로

 

1부터 n까지의 범위에서 n과 서로소인 자연수의 개수, 즉 오일러 피 함수 P[N]을 구하면 된다.

 

from sys import stdin
N = int(stdin.readline())
Nlist = []

# 인덱스값을 값에 넣기
for i in range(N+1):
    Nlist.append(i)

# 2번 수행
for i in range(2, N+1) :
    if Nlist[i] == i : #변경되기 전 값이라면
        for j in range(i,N+1,i): # 배수
            Nlist[j] = int(Nlist[j] - Nlist[j]/i)

print(Nlist[N])

우와~ 메모리 초과 별로 못 본 것 같은데

[백준 알고리즘] 메모리 초과 발생 이유 및 해결 방안

메모리 초과가 발생하는 이유 =>  '스택 오버플로우'가 발생하기 때문

 

 

'스택 오버플로우'

스택 포인터가 스택의 경계를 넘어설 때 / 호출 스택에서 이용 가능한 공간 이상을 사용하려고 시도할 때 발생

---

코드 고치기..

 

# 0

 P[n]만 필요하니 이전 오일러 피들은 안 구해도 된다!

P[n]에 영향을 주는 애들은 n의 약수들이므로, 

P[n]를 위한 계산(P[i] = P[i] -  P[i]/K)을 K가 n의 약수일 때 진행한다.

 

# 1

이때  n의 약수들인 K는 범위 2~n의 제곱근 까지만 진행하는데,

그 이유는 n의 제곱근 이상의 n의 약수는 "현재 리스트의 값 == 인덱스의 값(변경되지 않았음)일 시"의 조건에 어차피 어긋나게 될 것이기 때문이다. 

 

# 2

그렇다면 'n의 제곱근 이하의 n의 약수' 중 저 조건에 어긋나는 건 어떻게 가려낼까?

목표 수 n을 갱신함으로써 해결하면 된다.

현재 계산한 'n의 약수 k'로 n이 나누어질 때까지 나누어서(n= 45, k=3일 때 n을 5로 만들기) 9 같은 저 조건에 어긋나는 '원래 n'의 약수들이 계산되지 않을 수 있다.

 

# 3

반복문 종료 후 n이 1보다 크면 n이 마지막 소인수라는 뜻이므로 n으로 마지막 연산을 수행한다.

이 이거

이거 3번 무슨말인지 이해 안 된다 

아 집갈래

import math
from sys import stdin
# 0
N = int(stdin.readline())
result = N

for p in range(2, int(math.sqrt(N))+1) :# 1
    if N % p == 0:
        result -= result/p
	# 2
        while N % p == 0 :
            N/= p
# 3
if N > 1:
    result -= result/N

print(int(result))

 

---

+

어떤 분이 새 댓글을 달아서 내 8개월 전 질문을 다시 보게 됐는데 

이거 진짜 빵꾸 막아가면서 열심히 했는데ㅜㅜ 추억이다

글 읽기 - 99퍼센트에서 틀렸습니다 뜨는데 책상 뽀갤 뻔했어요