소수 찾기

❓문제

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

❗문제 정리

소수는 2부터 루트 자기자신까지의 수로 나누어지지 않는 수를 의미한다.
소수=전체 수-소수가 아닌 수

📑코드

import math
n=int(input())#n개의 수
nums=list(map(int, input().split()))

not_decimal=0

for num in nums:
  if num==1:#4보다 이하일때 소수가 아닌 경우
    not_decimal+=1
  for x in range(2, math.trunc(math.sqrt(num))+1):
    if num%x==0 and num!=2:
        not_decimal+=1
        break
print(n-not_decimal)

📝코드 설명

import math
n=int(input())#n개의 수
nums=list(map(int, input().split()))

sqrt를 사용하기 위해 math 라이브러리를 임포트 해준다.
수의 개수 n과 전체 수를 입력받아 nums에 넣어준다.

not_decimal=0

소수가 아닌 수를 세기 위한 변수 not_decimal

for num in nums:
  if num==1:#4보다 이하일때 소수가 아닌 경우
    not_decimal+=1
  for x in range(2, math.trunc(math.sqrt(num))+1):
    if num%x==0 and num!=2:
        not_decimal+=1
        break

• num이 1이면 소수가 아니기에 not_decimal+1
• num을 2부터 시작하여 루트 자기자신까지의 수로 나누어준다. 이때, trunc를 사용하는 이유는 sqrt값이 소수가 되므로 정수를 만들어주기 위해서 소수점 이하는 버리는 용도이다.
• 나누었을때, 값이 떨어지는데 num이 2가 아닌 경우, 소수가 아니므로 not_decimal+1을 해준다.
  여러번 더해지는 것을 방지하기 위해 일단 소수가 아니라고 판단하면 바로 루프를 빠져나온다.

print(n-not_decimal)

전체 개수에서 소수가 아닌 수의 개수를 빼주면 소수의 개수가 나온다.

🎖제출 결과

💡insight