[알고리즘] 백준 1978 소수 찾기 - S5

1. 2023.03.29 풀이

import sys
input=sys.stdin.readline

cnt=0
n=int(input())
arr=list(map(int, input().split()))

for i in arr:
    if i==1:
        cnt+=1
        continue
    for j in range(2, i):
        if i%j==0:
            cnt+=1
            break

print(n-cnt)

• 소수가 아닌 것 = 전체 개수 - 소수 개수
• 소수 개수 = 2부터 자기자신 전까지 나누어떨어지는 수가 있으면 소수 -> 카운팅

2. check point

• 에라토스테네스의 체
  여러개의 수가 소수인지 아닌지 판별할 때 사용하는 알고리즘
• 장점 : 매우 빠르게 동작
• 단점 : 메모리 많이 필요
  (따라서 에라토스테네스 -> 1,000,000 이내로 주어지는 경우가 많음)

• 2부터 N까지의 수 나열 후,
  처리하지 않은 가장 작은 수를 찾고,
  그의 배수들을 모두 제거.

import math

n=1000 #2~1000까지의 모든 수에 대해 소수 판별
arr = [True for i in range(n+1)] # 0,1 제외한 모든 수가 소수라고 초기화

#에라토스테네스 체 알고리즘
for i in range(2, int(math.sqrt(n)+1):   #2~ n의 제곱근까지 모든 수 확인
	if arr[i]==True:   #만약 i가 소수라면
    j=2
    while i*j<=n:   # i제외 i의 배수 합성수 처리
    	arr[i*j]=False
    	j+=1

#모든 소수 출력
for i in range(2, n+1):
	if arr[i]:
		print(i, end=" ")