[1978번] 소수 찾기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 에라토스테네스의 체

이 문제는 에라토스테네스의 체를 이해하고 그에 맞는 알고리즘을 작성 할 줄 안다면 해결할 수 있는 문제이다.

에라토스테네스의 체에 관한 자세한 내용은 다음 URL에서 확인할 수 있다.

http://www.crocus.co.kr/576

소스 코드 : 

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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#include <iostream> #include <cstdio>   using namespace std; #define MAX 1001 int arr[1002];   /* 에라토스테네스의 체 Sieve of Eratosthenes - 1부터 N까지 범위 안에 들어가는 모든 소수를 구하기 위해 에라토스테네스의 체를 이용한다. 1. 2부터 N까지 모든 수를 쓴다. 2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 3. 그 수를 지우고 소수로 저장한다. 4. 이제 그 수의 배수를 모두 지운다. */   void Eratosthenes(int num) {     int i;     //2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.     for (i = 2; i <= num; i++)     {         if (arr[i] != 0 && arr[i] != -1)             break;         else if (i == num)             return;     }     // 3. 그 수를 지우고 소수로 저장한다.     // (여기서는 0로 변환된 것이 소수, -1으로 변환된 것이 지워진 것)         arr[i] = 0;       // 4. 이제 그 수의 배수를 모두 지운다.     for (int j = 2; i*j <= num; j++)         arr[i*j] = -1;       Eratosthenes(num);     return; } int main() {     int n, cnt = 0;     scanf("%d", &n);          //1. 2부터 N까지 모든 수를 쓴다.     for (int i = 2; i <= MAX; i++)         arr[i] = i;       Eratosthenes(MAX);       arr[1] = -1; // 1은 소수가 아니다.       for (int i = 0; i < n; i++)     {         int val;         scanf("%d", &val);           // arr[val]값이 소수냐?         arr[val] == 0 ? cnt++ : 0;     }       printf("%d", cnt);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus