백준 1978번 파이썬 풀이 (소수찾기)

728x90

m=int(input())
list1=list(map(int,input().split()))

소수개수=0
소수체크=True

for i in list1:
    if i>1:
        소수체크=True
        for k in range(2,int(i**0.5)+1):
           if i%k ==0 : #나눠 떨어지지 않으면 (나머지가 1이상이면)
              소수체크 = False
              break  #소수가 아니므로 넘어간다.
        if 소수체크==True:
            소수개수 +=1
print (소수개수)

소수는 1과 자기 자신만을 약수로 갖는 수입니다.

따라서 어떤 자연수 N이 소수인지 아닌지 판별하기 위해서는 2부터 N-1까지의 모든 수로 N을 나눠보아야 합니다.
하지만 이러한 방식으로 모든 수를 나누어보는 것은 비효율적입니다.

N이 K로 나누어 떨어진다는 것은 N = a × b의 형태로 나타낼 수 있습니다.
여기서 a와 b는 모두 N의 약수입니다. 그리고 a와 b 중 적어도 하나는 √N보다 작거나 같습니다.
예를 들어 20은 2 × 10, 4 × 5로 나타낼 수 있으며, √20은 대략 4.47이므로 4보다 작거나 같은 수들로 20의 소수 여부를 판단할 수 있습니다.

따라서 2부터 N의 제곱근까지의 수들만 나눠보면 N이 소수인지 아닌지 판별할 수 있습니다.
그 이유는 N의 제곱근보다 큰 수들로는 N을 나눌 수 없기 때문입니다.
만약 N이 제곱근보다 큰 수 a로 나눠진다면, 그 나머지는 b = N / a라는 작은 수가 되며,
이 때 b는 a보다 작으므로 이미 검사한 수들 중 하나로 나누어떨어질 것입니다.
따라서 a 이상의 수로 나누어떨어지는지 확인할 필요가 없습니다.

예를 들어, 25가 소수인지 판별하려면 2부터 5까지의 모든 수로 나누어보아야 합니다.
하지만 25의 제곱근은 5이므로 2부터 5까지의 수만 나눠보면 됩니다.
2, 3, 4로 나누어봤을 때 나머지가 0이 되는 것이 없으므로 25는 소수입니다.

이러한 원리를 이용하여, 2부터 N의 제곱근까지의 수들만 나눠보면서 N이 소수인지 아닌지 판별할 수 있습니다.
131의 제곱근은 대략 11.45입니다. 따라서 2부터 11까지의 모든 수로 131을 나누어보면 됩니다.

2로 나누어보면, 131 ÷ 2 = 65.5가 되므로 정수가 아닙니다.
3으로 나누어보면, 131 ÷ 3 = 43.67가 되므로 정수가 아닙니다.
4로 나누어보면, 131 ÷ 4 = 32.75가 되므로 정수가 아닙니다.
5로 나누어보면, 131 ÷ 5 = 26.2가 되므로 정수가 아닙니다.
6로 나누어보면, 131 ÷ 6 = 21.83이 되므로 정수가 아닙니다.
7로 나누어보면, 131 ÷ 7 = 18.71이 되므로 정수가 아닙니다.
8로 나누어보면, 131 ÷ 8 = 16.37이 되므로 정수가 아닙니다.
9로 나누어보면, 131 ÷ 9 = 14.56이 되므로 정수가 아닙니다.
10으로 나누어보면, 131 ÷ 10 = 13.1이 되므로 정수가 아닙니다.
11로 나누어보면, 131 ÷ 11 = 11.91이 되므로 정수가 아닙니다.
따라서 131은 2부터 11까지의 어떤 수로도 나누어떨어지지 않으므로, 131은 소수입니다.

이처럼, N의 제곱근까지의 모든 수로 나누어보면서 나머지가 0인 경우가 없으면 해당 수는 소수입니다.
이 방법은 N이 매우 큰 경우에도 효율적으로 동작합니다.

11보다 큰 수로 나눠볼 필요가 없는 이유는,
11보다 큰 수는 11보다 작은 수와 곱하여 만들어질 수밖에 없기 때문입니다.
예를 들어, 13은 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12와 곱하여 만들어질 수 없으므로,
11보다 큰 수로 나누어봐야 의미가 없습니다.

N이 소수가 아닌 경우, N은 N = a × b의 형태로 나타낼 수 있습니다.
여기서 a와 b는 모두 N의 약수입니다.
따라서 a와 b 중 적어도 하나는 √N보다 작거나 같습니다.
그리고 a와 b 중 큰 수는 N / (√N) = √N입니다.

따라서 2부터 √N까지의 수로 나누어보면서 나머지가 0인 경우가 없으면 해당 수는 소수입니다. 그
이유는 √N보다 큰 수는 N의 약수가 아니기 때문입니다.
만약 N이 √N보다 큰 수 a로 나눠진다면, 그 나머지는 b = N / a라는 작은 수가 되며,
이 때 b는 a보다 작으므로 이미 검사한 수들 중 하나로 나누어떨어질 것입니다.
따라서 a 이상의 수로 나누어떨어지는지 확인할 필요가 없습니다.

그렇기 때문에, 11보다 큰 수로는 나눠볼 필요가 없는 것입니다.
다시 말해, 2부터 11까지의 수로 나누어보면서 나머지가 0인 경우가 없으면 해당 수는 소수입니다.