[4월 - 코딩테스트] 정수론 문제모음

 

1. 소수 구하기

• 에라토스테네스의 채 원리 : 구하고자 하는 소수의 범위만큼 1차원 리스트 생성 -> 2부터 시작하고 현재 숫자가 지원진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지움 -> 리스트 끝까지 반복한 후 리스트에 남아있는 수 출력
• for 문을 돌면서 이미 소수가 아니라고 판별된 것 ( A[i] == 0 ) 인 것은 continue로 건너뛰고
• for i in range(i+i, m+1, i) 코드를 통해 배수를 계속해서 지워나감
• 마지막으로 0 이 아닌 것은 출력하기 

import math
# 에라토스테네스의 체 원리 이용
n,m = map(int, input().split())
A = [0] * (m+1)

for i in range(2,m+1) :
    A[i] = i

for i in range(2, int(math.sqrt(m)) + 1) :
    if A[i] == 0 :
        continue  # 0일 경우 코드 시행 건너뛰기
    for j in range(i+i, m+1, i) : # 배수 지우기
        A[j] = 0

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

 

---

 

2. 소수&팰린드롬 수 중에서 최솟값 찾기

# 소수&팰린드롬
import math
n=int(input())

# 소수 리스트 만들기
A = [0] * 1000001

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

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

# 팰린드롬 판별 함수
def isPalinrome(target) :
    temp = list(str(target))
    s = 0
    e = len(temp) -1
    while s<e :
        if temp[s] != temp[e] :
            return False
        else :
            s += 1
            e -= 1

    return True

i = n

while True :
    if A[i] != 0 :
        result = A[i]
        if isPalinrome(result) :
            print(result)
            break
        i += 1

 

---

 

3. 소수 찾기

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

import math
def number(n) :
    for i in range(2,int(math.sqrt(n)) + 1 ) :
        if n%i == 0:
            return False
    if n == 1 :
        return False
    return True


# 입력받기
n = int(input())
A = list(map(int, input().split()))
count = 0
for i in range(n) :
    if number(A[i]) :
        count +=1
print(count)

 

 

---

4. 최대공약수와 최소공배수

• 유클리드 호제법을 이용한 풀이
• 그냥 유클리드 호제법을 이용해서 최대공약수, 최소공배수 구하는 방법을 거의 암기하고 싶이 알고있으니 구현이 매우 쉬웠다. 

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

n,m = map(int, input().split())

def gcd(a,b) :
    if b == 0 :
        return a
    else :
        return gcd (b, a%b)

# 최대공약수
print(gcd(n,m))
# 최소공배수
print(int((n*m) / (gcd(n,m))))

 

---

5. 최소공배수

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

def gcd(a,b):
    if b == 0:
        return a
    else :
        return gcd(b, a%b)


t = int(input())
for i in range(t):
    n,m = map(int, input().split())
    print(int((n*m)/(gcd(n,m))))

 

---

 

6. 소인수분해

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

def numbers(n) :
    i = 2
    A = list()
    while i <= n :
        if n%i == 0 :
            A.append(i)
            n = n/i
        else :
            i = i+1

    return A

n = int(input())
k = numbers(n)

for i in k :
    print(i)