[Algorithm][C언어] 백준 1978번: 소수 찾기

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

1978번: 소수 찾기

 

 

문제

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

 

입력

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

 

출력

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

 

관련 개념

이 문제는 에라토스테네스의 체 알고리즘을 사용하여 풀이하는 문제이다. 

꼭 저 알고리즘을 사용하지 않아도 문제가 풀리긴 한다.

 

에라토스테네스의 체

• 소수를 판별하는 알고리즘
• 소수들을 대량으로 빠르고 정확하게 구하는 방법

 

에라토스테네스의 체 원리

• 가장 먼저 소수를 판별할 범위만큼 배열을 할당한 뒤에 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법
  1. 배열을 생성하여 초기화
  2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지우기
     • 지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛰기
     • 1은 소수가 아니므로 2부터 시작!
  3. 2부터 시작하여 남아있는 수를 모두 출력

 

코드

#include <iostream>
#define MAX 1001

int a[MAX];

int main() {
    //1은 소수가 아니므로 따로 판별
    a[1]++;
    int n, tmp, result = 0;
    scanf("%d", &n);
    for(int i = 2; i < MAX; i++) {
        for(int j = i + i; j < MAX; j += i) {
            if(a[j] == 1) 
            	continue;
            else 
            	a[j]++;
        }
    }

    for(int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        if(!a[tmp]) 
        	result++;
    }
    printf("%d", result);

    return 0;
}

 

참고

에라토스테네스의 체 개념

https://velog.io/@max9106/Algorithm-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

 

코드 

https://coding-maggot.tistory.com/112