백준 1978 소수찾기

소수 찾기 성공분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	45943	21518	17842	48.519%

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1 

4
1 3 5 7

예제 출력 1 

3

문제출처 https://www.acmicpc.net/problem/1978

문제해결순서

1. 소수가 되는 조건을 생각한다

2. 반복문을 돌려서 소수가 되는 조건이면 소수개수를 증가시킨다

알아야 할 지식

어떤수가 소수가 되려면 나눠지는게 1이랑 자기 자신이여야한다

Colored By Color Scripter™

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <stdio.h>  #include <string.h>    int main(void)  {      int N,i,j,IN[100],num=0;     scanf("%d",&N);          for(i=0 ; i<N ; i++)     {         scanf("%d",&IN[i]);         if(IN[i]==2)             num++;     }              for(i=0 ; i<N ; i++)     {         for(j=2 ; j<=IN[i] ; j++)         {             if(IN[i]%j == 0)                 break;                          if(j == IN[i]-1)                 num++;         }     }     printf("%d",num); }

8~14 번째줄 : 숫자를 입력받고 2이면 소수니까 1 증가시킨다

16~28번째줄 : 2이후에 나오는 수가 소수이면 1 증가시킨다

18번째줄 : j=2부터 시작하는 이유는 j=1이면 20번째 줄에서 항상 break 시킨다. 그래서 j=2부터 시작하게 한다. 대신 2가나오면 13번째줄에서 1증가시키니 상관없다

20번째줄 : 소수가 아니면 break시킨다

23번째줄 : 숫자-1이랑 j가 같으면 소수다. 왜냐하면 숫자는 11이고, j가 10이라고 했을 때 10다음에 11이라서 소수다.