[백준] 1978번 (python 파이썬)

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

1978번: 소수 찾기

 

import sys

testcase = int(input())
input_number = list(map(int,sys.stdin.readline().split()))
# 가장 높은 수 기준으로 에라토스테네스의 체를 만든다.
# 나머지 수는 만들어 놓은 에라토스테네스의 체에 인덱스로 접근해서 소수인지 판별한다.
prime_number = [True] * max(input_number)
prime_number[0] = False	# 1은 소수가 아니다.

i = 1	# 2부터 반복한다.
# 현재 가리키는 수의 배수에 해당하는 인덱스를 갖는 값들을 False로 변경한다.
while i < len(prime_number):
  if prime_number[i]:
    j = (i + 1) * 2 -1
    while j < len(prime_number):
      prime_number[j] = False      
      j += (i + 1)
  i += 1

count = 0
for n in input_number:
  if prime_number[n-1]:
    count += 1
print(count)

 

2의 배수에 접근할때 인덱스는 1, 3, 5, 7...

3의 배수에 접근할때 인덱스는 2, 5, 8, 11...

헷갈릴수 있다.

이 경우 빈 값을 앞에 하나 넣어서 인덱스와 수를 일치시키면 된다.

그 후 찬찬히 생각하며 정리하면 꿀.

근데 굳이 그렇게 안해도 별 차이 안날듯 하다.

 

아래는 while문 대신 for문으로 작성한 코드이다.

import sys

testcase = int(input())
input_number = list(map(int,sys.stdin.readline().split()))
prime_number = [True] * max(input_number)
prime_number[0] = False

for i in range(1, len(prime_number)):
  if prime_number[i]:
    for j in range((i+1)*2 -1, len(prime_number), i+1):
      prime_number[j] = False      
      

count = 0
for n in input_number:
  if prime_number[n-1]:
    count += 1
print(count)

 

그리고 한가지 트릭이 있다.

 n이  p*q로 표현될 때 한 수는 항상 n^(1/2)이하, 다른 한 수는 n^(1/2) 이상이라는 점을 이용하면 더욱 최적화된다. 

import sys

testcase = int(input())
input_number = list(map(int,sys.stdin.readline().split()))
prime_number = [True] * max(input_number)
prime_number[0] = False

m = int(len(prime_number) ** 0.5)
for i in range(1, m + 1):
  if prime_number[i]:
    for j in range((i+1)*2 -1, len(prime_number), i+1):
      prime_number[j] = False      
      

count = 0
for n in input_number:
  if prime_number[n-1]:
    count += 1
print(count)