[백준] 1978번 소수 찾기 - 파이썬(Python)

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

1978번: 소수 찾기

 

문제

 

21.03.05 접근법

 

에라토스테네스의 체 이용

 

 

21.03.05 코드

N=int(input())
arr=list(map(int,input().split()))

prime={}
cnt=0

for i in range(1,1001):
    prime[i]=True

prime[1]=False

for i in range(2,int(1000**0.5)+1):
    if prime[i]==True:
        for j in range(i+i,1001,i):
            prime[j]=False



for i in arr:
    if prime[i]==True:
        cnt+=1

print(cnt)

 

21.08.10 접근법

 

###다시 풀기! 검색해서 풀음.###

 

에라토스테네스의 체 이용

 

[풀이순서]

1. 입력받은 값 중 최댓값 구함.

2. 2부터 최댓값의 루트까지 반복문 실행

(위키백과에 의하면 m=a*b일 때, a와 b 중 하나는 무조건 루트 m 이하라고 한다. 이에 루트 m까지만 소수를 판별하면 됨.)

3. 그 중, 해당 값이 True이면 최댓값까지 해당 값의 배수들을 False로 변경

4. 그 결과, True면 소수 / False면 소수가 아님이 구분됨.

 

 

21.08.10 코드

import sys

N=int(input())
arr=list(map(int,sys.stdin.readline().strip().split()))

max_num=max(arr)
prime=[True]*(max_num+1)
prime[1]=False

for i in range(2,int(max_num**0.5)+1):
    if prime[i]==True:
        for j in range(i*i,max_num+1,i):
            prime[j]=False

cnt=0
for i in arr:
    if prime[i]==True:
        cnt+=1

print(cnt)