103. 소수 찾기
문제
주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.
입력
첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.
출력
주어진 수들 중 소수의 개수를 출력한다.
예제 입력 1
4
1 3 5 7
예제 출력 1
3
<내 풀이>
n=int(input())
m=list(map(int, input().split()))
cnt = 0
a=[0]*1001
a[1]=1 #소수가 아닌건 체크
#1000까지의 수 중에서 소수 아닌 애들은 1, 소수인 애들은 0으로 배열채움
for i in [2,3,5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,71, 73, 79, 83, 89, 97] :
for j in range(i,1001, i) :
if(a[j]==0) :
a[j]=1
for i in [2,3,5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,71, 73, 79, 83, 89, 97] :
a[i] = 0
for k in m :
if a[k]==0 :
cnt+=1
print(cnt)
<다른 분의 풀이 or 내 틀린 풀이, 문제점>
출처 : 출처
<반성 점>
<배운 점>
-
위와 같이 유동적으로 입력들이 가로로 주어지면 list로 받아준다
-
아래는 a라는 리스트로 받아준 모양
a=list(map(int, input().split())) -
소수 찾기는 무조건 에라스토테네스의 체 방식으로 찾아내기
=> 방식 설명, 복습 :기본적인 소수들의 배수는 무조건 소수가 아님
2의 배수는 모두 소수 아님
1도 소수 아님
기본적 소수들의 예 2,3,5,7,11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67,71, 73, 79, 83, 89, 97
이때 100 이하의 소수들은 11^11 = 121 이므로 2,3,5,7의 배수가 아닌 애들은 다 100이하의 소수라고 볼 수 있겠삼 121 이상 부터는 2,3,5,7,11의 배수가 아니여야 소수고..쭉쭉
이때 에라스토테네스는 배열 만들고 채워넣는 방식으로 해결하기
for i in range(2, 범위끝, i)이렇게 해서 소수를 찾으면 위와 같이 range 돌리면서 소수의 배수들의 배열칸엔 1 채워주기
소수는 1 안들어감
