1978번 소수 찾기

 

 

 

1) 사이트

1978번: 소수 찾기

 

 

 

2) 문제

문제는 정말 간단합니다. 입력 받은 숫자 중 소수가 몇 개인지 출력을 해주면 됩니다.

근데 소수란 무엇인지부터 아셔야겠죠?

 

소수는 약수가 1과 자기자신밖에 없는 수를 소수라고 하고, 그 외에 수를 합성수라고 합니다.

예를 들어 11과 같은 경우는 1,11의 약수를 갖기 때문에 소수이고,

12와 같은 경우는 1,2,3,4,6,12의 약수를 갖기 때문에 합성수 입니다.

 

저도 고민 많이 했습니다... 그렇다면 소수를 판정지을 만한 식이 있나?

지식백과에도 쳐보기도 하고요 ㅎㅎ

소수와 합성수

 

근데 문제 하단을 보면 알고리즘 분류에도 나와있고, 지식백과에 연관 지식으로도 나와있는 이것!

바로 '에라토스테네스의 체' 입니다.

솔직히 이거보고도 몰라서 더 찾아보니 소수는 이렇게 찾습니다.

 

만약 11이라는 수가 주어졌을 때 2~10까지의  수 즉, 2~나자신-1까지의 숫자로 나누었을 때 그 어떤 수로도 나누어 떨어지지 않으면, 그 수는 소수 입니다.

 

반면 12는 2~11까지 했을 때 벌써 2에서 나누어 떨어지므로 합성수라는 것을 알 수 있겠죠?

 

 

 

3) 파이썬 코드

#소수의 갯수를 구하라
#소수는 2~나자신-1까지했을 때 나 자신이 안나눠떨어지면 소수
each=int(input())
number=[]*each
flag=0 #소수면0 아니면1
result=0

number=map(int,input().split())

for i in number:
    for j in range(i-1,1,-1):
        if(i%j==0):
            flag=1
            break
        
    if flag==1 or i==1:
        flag=0
            
    else:
        result=result+1

            
print(result)

 

3-1) 선수 지식

파이썬 코드를 이해하기 위해 알아야 할 선수 지식이 있습니다.

 

1. map의 사용법

아직 파이썬 초보인 저는 ㅎㅎ...map을 input으로 받는 즉, 문자열로 받아들여지는 것들을 int형으로 치환해서 저장하고 싶을 때 사용하고 있습니다.

list_a=map(int, input().split())

즉, 위처럼 어떤 리스트에 내가 받은 값은 숫자로 저장하고 싶을 때 사용하고 있습니다.

많은 분들이 시도해보셨겠지만, list_a=int(input().split) 이런 형태를 안되는 것 아시죠?!

 

 

 

3-2) 설명

 

1. 사용할 변수를 선언 및 초기화 해줍니다.

flag=0 #소수면0 아니면1
result=0

flag는 소수이면 0, 아니면 1을 나타내는 역할을 할 겁니다.

result는 소수가 총 몇 개인지 나타내는 역할을 할 겁니다.

 

2. 몇 개 수를 입력할 것인지 받고, 그 만큼의 수를 리스트에 저장해줍니다.

each=int(input())
number=[]*each

number=map(int,input().split())

 

3. 입력받은 숫자 리스트에서 숫자를 하나 씩 뺄 겁니다.

for i in number:

 

4. 그리고 뺀 숫자 하나를 대상으로 2~자기자신-1까지 나누어 떨어지는 것이 있는 지 확인합니다.

for i in number:
    for j in range(i-1,1,-1):
        if(i%j==0):
            flag=1
            break

나누어 떨어진다면 그것은 합성수 이므로 flag=1 (합성수)로 변경해주고 반복문을 멈춥니다.

 

5. flag==1이거나 해당 숫자가 1일 경우는 결과값을 추가하지 않습니다.

if flag==1 or i==1:
    flag=0

1은 소수가 아닌 것 알고 계시죠?!

 

6. 그 외의  숫자들은 소수로 생각하고, 결과값에 1을 추가해줍니다.

else:
    result=result+1

 

 

7. 전체 반복문이 다돌아간 후 결과값을 출력해줍니다.

print(result)

 

 

 

4) c언어

없음

 

---

궁금한 점이나 공유할 정보가 있다면 댓글로 남겨주세요 *^^*

끝!