정수론-에라토스테네스의 체

이론

📖 소수
약수가 1과 자기자신뿐인 자연수.

#소수판별

import sys
input=sys.stdin.readline

n=int(input())
count=0

for i in range(1,n+1):
    if(n==1):
        count=0
    if(n%i==0):
        count+=1

if(count==2):
    print("%d 는 소수입니다."%n)
else:
    print("%d 는 소수가 아닙니다." % n)
    

📖 에라토스테네스의 체
소수를 판별할 때 사용된다.

1) 구하고자 하는 소수의 범위만큼 1차원리스트를 작성한다.
2) 2부터 시작해서 끝까지, 숫자의 배수에 해당하는 수들을 리스트에서 지운다.(처음 선택된 숫자는 지우지않는다.)
3) 리스트에 남아있는 수들을 출력한다.

📍 백준 1929 참고 (🔗백준 1929 문제)

• 아래와 같이 코드를 작성시, 문제의 주어진 조건에 따라 시간초과가 발생할 수 있다.(백준 1929 문제의 같은 경우)

# 소수판별
# m이상 n이하의 소수를 모두 출력.

import sys
input=sys.stdin.readline

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

def prime(num):
    count=0
    for i in range(1,num+1):
        if(num==1):
            count=0
        if(num%i==0):
            count+=1
    if(count==2):
        print(num)

for i in range(m,n+1):
    prime(i)

• 아래와 같이 위의 문제를 에라토스테네스 방법을 이용하여 시간을 줄일 수 있다.

# 소수판별
# m이상 n이하의 소수를 모두 출력.

import math
import sys
input=sys.stdin.readline

m,n=map(int,input().split())
arr=[0]*(n+1)

for i in range(2,n+1):
    arr[i]=i

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

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

문제풀이

📖 백준 1456 (🔗백준 1456 문제)

✏ 에라토스테네스의 체 사용.

✏ n^k 와 b의 값이 아니라 n과 b/n^(k-1)을 비교해야된다.

• 아래와 같이 코드 작성시 인덱스오류가 발생한다. 따라서, n^k 와 b의 값이 아니라 n과 b/n^(k-1) 을 비교해야된다.

import math
import sys
input=sys.stdin.readline

a,b=map(int,input().split())
arr=[0]*(10000001)
count=0

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

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

for i in range(a,b+1):
    if(arr[i]!=0):
        j=2
        while arr[i]**j<=b:
            j+=1
            count+=1

print(count)

• prime값(현재소수값) 설정해서 이항정리로 문제를 해결할 수 있다.

import math
import sys
input=sys.stdin.readline

a,b=map(int,input().split())
arr=[0]*(10000001)
count=0

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

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

for i in range(2,10000001):
    if(arr[i]!=0):
        prime=arr[i]   #prime=현재 소수값
        while arr[i]<=b/prime:
            if(a/prime<=arr[i]):
                count+=1
            prime*=arr[i]

print(count)

📖 백준 1747 (🔗백준 1747 문제)

✏ 에라토스테네스의 체

✏ palindrome

#소수-에라토스테네스의 체
#팰린드롬

import math
import sys
input=sys.stdin.readline

n=int(input())
arr=[0]*(10000001)

def palindrome(num):
    test=list(str(num))
    start=0
    end=len(test)-1
    while start<end:
        if(test[start]!=test[end]):
            return False
        start+=1
        end-=1
    return True

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

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

while 1:
    if(arr[n]!=0):
        result=arr[n]
        if(palindrome(result)==True):
            print(result)
            break
    n+=1

📖 백준 1016 (🔗백준 1016 문제)

✏ min의 최댓값이 큰 것 같지만, 문제를 풀때는 min과 max사이의 수들 안에서 구하기 때문에 1,000,000 의 데이터만 확인하면 된다.

✏ 제곱수 판별을 반복문으로 구할 시 시간초과가 발생할 수 있으므로, 에라토스테네스의 체를 사용한다.

✏ "제곱이 아닌 수" 는 어떤 수 x가 1보다 큰 제곱수로 나누어떨어지지 않는 수를 말한다. 문제를 풀 때 주의해야 될 포인트는 나누어떨어지지 않는 수 이다. 따라서, 제곱수와 제곱수의 배수를 모두 제거하고 남은 수들을 구해야 된다.

✏ start인 인덱스를 구할 때, 최솟값%제곱수==0 인 것과 최솟값%제곱수!=0 인 것을 구별하여 각각 조건에 맞는 start점을 지정해야된다.

#에라토스테네스의 체 사용 ---> 제곱수의 배수형태로 탐색해 시간복잡도를 최소화한다.

import math
import sys

input = sys.stdin.readline

min, max = map(int, input().split())
arr=[0]*(max-min+1)
count=0

#"제곱인 수"(어떤 수 x가 1보다 큰 제곱수로 나누어떨어질떄)들을 해당 인덱스에 1로 치환한다.
for i in range(2,int(math.sqrt(max)+1)):
    pow=i**2
    if(min%pow==0):
        start=int(min/pow)
    else:
        start=int(min/pow)+1
    for j in range(start,int(max/pow)+1):
        arr[int(j*pow-min)]=1

for i in range(0,max-min+1):
    if arr[i]==0:
        count+=1

print(count)

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준