[알각코] 백준 2581번 - 소수

백준 2581번

M = int(input())
N = int(input())

a = [False, False] + [True]*(N - 1)
primes = []

for i in range(2, N+1):
    if a[i]:
        if i >= M:
            primes.append(i)
    for j in range(2*i, N+1, i):
        a[j] = False

if len(primes) == 0:
    print(-1)
else:
    print(sum(primes))
    print(primes[0])

에라토스테네스의 체 python 코드를 참고하여 풀었당

에라토스테네스의 체

범위에서 합성수를 지우는 방식으로 소수를 구하기 위해 에라토스테네스가 제시한 방법이다.

• 1은 제거
• 지워지지않은 수 중 제일 작은 수 2를 소수로 채택, 그 후 2의 배수를 모두 지운다.
• 지워지지않은 수 중 제일 작은 수 3을 소수로 채택, 나머지 3의 배수를 모두 지운다.
• 지워지지않은 수 중 제일 작은 수 5을 소수로 채택, 나머지 5의 배수를 모두 지운다.
• …반복!

n = 1000

## 첫번째 수 0, 두번째 수 1 이어서 False 리스트를 먼저 넣어주고 시작
a = [False, False] + [True]*(n - 1)
primes = []

## 숫자 2부터 False 만들기 시작
for i in range(2, n+1):
    if a[i]:
        primes.append(i)
    ## i의 배수 다 False 만들기 (n+1까지)
    for j in range(2*i, n+1, i):
        a[j] = False

print(primes)

단순무식한 코드

n=100

def isPrime(a):
  if(a<2):
    return False
  for i in range(2,a):
    if(a%i==0):
      return False
  return True

for i in range(n+1):
  if(isPrime(i)):
    print(i)

소수인지 판별하는 함수를 만들어 모든 수를 돌아서 소수인지 체크한다!

소수 판별하는 법

• 2보다 작다 => false
• 2부터 들어온 수까지 들어온 수에서 i를 나눈다 그 중 == 0 일경우 => false
• 0이 아니면 True

Reference

• 소수 구하기 - 에라토스테네스의 체