실력키우기 소수구하기(C++)

1901 : 소수 구하기

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 841회    시도횟수: 3109회   

소수(prime number)란 2이상의 수로써 1과 자기 자신 외에는 약수를 갖지 않는 수를 의미한다. 임의의 M값에 대하여 M에 가장 가까운 소수를 구하는 프로그램을 아래 조건에 따라 작성한다.

 

첫 번째 줄에는 처리해야 할 수의 개수 N을 입력 받는다. (N은 100이하의 정수) 

다음 줄에는 처리해야할 수 N개(M1부터 Mn까지)를 한 줄에 한 개씩 차례로 입력 받는다. (Mi 는 1,000,000 이하의 양의 정수) 

데이터의 크기가 주어진 범위를 벗어나는 입력은 없다.

임의의 값 Mi에 대해 차이가 가장 작은 소수를 구하여 출력한다. 

만약 차이가 같은 소수가 여러 개이면 작은수부터 모두 출력한다.

[Copy] 2 8 15

[Copy] 7 13 17

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 68 69 70 71 72 73 74 75 76

/**************************************************************     Problem: 1901     User: a132034     Language: C++     Result: Success     Time:230 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> using namespace std; #define max 1000000 int main() {     int n;     int *m;     bool flg;     bool pf, mf;     cin >> n;     m = new int[n];       for (int i = 0; i < n; ++i)         cin >> m[i];       for (int i = 0; i < n; ++i)     {         flg = false;         pf = false;         mf = false;         for (int j = 0; j < abs(max - m[i]); ++j)         {             if (mf || pf)             {                 cout << endl;                 break;             }               mf = pf = true;                           if (m[i] - j > 1)             {                                  for (int mi = 2; mi < m[i] - j; ++mi)                 {                       if ((m[i] - j) % mi == 0)                     {                         pf = false;                         break;                     }                 }                                   if (pf)                     cout << m[i] - j << " ";             }               if (m[i] + j <= max)             {                                  for (int mi = 2; mi < m[i] + j; ++mi)                 {                     if ((m[i] + j) % mi == 0)                     {                         mf = false;                         break;                     }                 }                 if (mf && j != 0)                     cout << m[i] + j;             }           }       }     return 0; }

소수 구할때는 소수의 정의에 따라 1과 자기자신을 제외하고는 나누어지면 안되므로 

입력받은 수 보다 작은 수 까지만 나누며 나누어질 경우 바로바로 break로 빠져나오면 쓸데없는 연산을 줄일 수 있다. 

bool변수는 루프를 멈추기 위한 변수. 그외 특이사항 없음.