[BOJ] 1978번 : 소수 찾기

🔒 문제

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

⌨ 입력

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

🖨 출력

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

📚 예제

Ex1)

4
1 3 5 7

3

📌 풀이

소수 찾는 법

1. n이 1이면 소수 아님
2. n이 2가 아닌 짝수면 소수 아님 (2이면 소수)
3. n을 나눌 수 있는 1이 아닌 첫 홀수가 자기 자신이면 소수임

🔑 c언어 코드

#include <stdio.h>

int main()
{
    int N, n; // N은 수의 개수, n은 그 수를 저장
    int ans = 0;
    int i, k, j;
    scanf("%d", &N);
    for (i = 0; i < N; i++)
    {
        scanf("%d", &n);
        if (n == 1)
            continue;
        else if (n % 2 == 0)
        {
            if (n / 2 == 1)
                ans++;
        }
        else
        {
            j = 0;
            while (1)
            {
                k = (j++) * 2 + 3;
                if ((n / k != 1) && (n % k == 0))
                    break;
                else if (k == n)
                {
                    ans++;
                    break;
                }
            }
        }
    }

    printf("%d", ans);

    return 0;
}