[기초-소수] ★백준 1978번 소수 찾기 with Python3

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

1978번: 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

예제 입력

4

1 3 5 7

내 풀이

import math
n = 1000
a = int(math.sqrt(n))

primelist = []
for i in range(2, n-1):
    primelist.append(i)

primeN = []
for i in range(2, a+1):
    primeN.append(i)

for i in range(4, a):
    for j in range(2, i):
        if i % j == 0 and i in primeN:
            primeN.remove(i)
power = 2
for j in range(len(primeN)):
    power = primeN[j]
    for i in range(2, int(n)):
        c = power*i
        if c in primelist:
            primelist.remove(c)

sth = int(input())
a = list(map(int, input().split()))

set1 = set(primelist)
set2 = set(a)

print(len(set1 & set2))

해설

에라토스테네스의 체!

더럽게 비효율적이라는것은 딱보면 척이다

n값 안의 모든 prime을 찾는다. 루트n까지는 for문을 돌린다. 그리고 에라토스테네스의 체를 사용. 이미 만들어진 1부터 1000의 숫자가 들어있는 list에서 소수 이외를 전부 없앤다. 

 

정답 풀이 -에라토스테네스의 체

import math
num_count = int(input())
num_list = list(map(int, input().split(' ')))
natural_num = list(range(2,1001))                       # 자연수 범위를 정한다.(소수는 1이상인 정수이기때문에 1은 뺀상태)
count = 0
 
if len(num_list) == num_count:
    for i in range(2, math.ceil(math.sqrt(1000))):      # p²≥100인 p의 배수(p를 제외한)까지만 지우면 된다.
        for j in natural_num:            
            if j / i == 1:                              # 자기 자신으로 나뉘는것은 제외
                pass           
            elif j % i == 0:                            # 그 이외에 나뉘는 수가 존재하면
                natural_num.remove(j)                   # 그 수는 정수 리스트에서 제거
for k in num_list:
    if k in natural_num:                                # num_list에 natural_num이랑 중복되는 수가 있다면 count +1
        count += 1
print(count)

출처:https://ksw626.tistory.com/87

해석

pass 가 신기.

for, if k in iterable은 정말 여전히 충격적이다.

 

정답 풀이 -소수 판정식

n = int(input())
numbers = map(int, input().split())
sosu = 0
for num in numbers:
    error = 0
    if num > 1 :
        for i in range(2, num):  # 2부터 n-1까지
            if num % i == 0:
                error += 1  # 2부터 n-1까지 나눈 몫이 0이면 error가 증가
        if error == 0:
            sosu += 1  # error가 없으면 소수.
print(sosu)

출처:https://ooyoung.tistory.com/92

 

해석