[백준/python] 1978_소수찾기

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

1978번: 소수 찾기

 

작성한 코드에 대한 전체적인 내용 풀이

1. 

문제에서 주어지는 수들이 1000 이하의 자연수이므로, 1000까지 범위의 소수리스트를 따로 구했습니다. 문제에 최적화된 풀이는 아니나, 범위만 조정하면 다른 문제에도 바로 적용할 수 있습니다.

 

2. 소수란?

소수는 1과 자기 자신으로 나눌 때만 나누어 떨어지는 자연수이다. 즉 1과 자기 자신을 제외한, 다른 수로 나누었을 때 나머지가 있다면 소수이다. 

 

 

solv 1.

1. flag

for문 위의 flag는 i가 2일 때를 포함시켜주기 위해 만들어졌다. 2도 소수인데, for문에서 2를 확인할 수 없다. (int(2**0.5)+1 = 2 이므로, range(2,2)가 됨)

 

2. for문의 범위

i가 1을 제외한 수로(2부터) 나누어지는지 확인한다. 다만 소수가 아니라면 제곱근의 범위 안에서 약수가 나와 걸러진다. 예를 들어 16의 약수는 1,2,4,8,16인데, 제곱근의 범위(4) 내에서 약수가 나온다.

n = int(input())

prime = []
for i in range(2,1001):
    flag = True
    for j in range(2, int(i**0.5)+1):
        if i % j == 0:
            flag = False
            break
    if flag:
        prime.append(i)

test_n = list(map(int, input().split()))
count = 0
for test in test_n:
    if test in prime:
        count += 1
print(count)

 

 

solv 2. 에라토스테네스의 체

[과정]

1. 자연수 범위의 수를 나열한다. (2~n)

2. 소수의 배수를 지운다.

3. '2' 과정을 반복한다. (p>= n**0.5: p의 제곱이 n보다 작거나 같을 범위까지, 즉 p가 n의 제곱근보다 작거나 같을 때까지)

 

n = int(input())

prime = [False, False] + [True] * (999)  # true이면 소수
for i in range(2, int(1001 ** 0.5) + 1):
    if prime[i]:
        for j in range(2*i, 1001, i):
            prime[j] = False

test_n = list(map(int, input().split()))
count = 0
for test in test_n:
    if prime[test]:
        count += 1
print(count)