๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โœจ Algorithm

[๋ฐฑ์ค€/C++] 2581๋ฒˆ : ์†Œ์ˆ˜

by nitronium102 2021. 8. 6.

๋ฌธ์ œ

์ž์—ฐ์ˆ˜ M๊ณผ N์ด ์ฃผ์–ด์งˆ ๋•Œ M์ด์ƒ N์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์†Œ์ˆ˜์ธ ๊ฒƒ์„ ๋ชจ๋‘ ๊ณจ๋ผ ์ด๋“ค ์†Œ์ˆ˜์˜ ํ•ฉ๊ณผ ์ตœ์†Ÿ๊ฐ’์„ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

์˜ˆ๋ฅผ ๋“ค์–ด M=60, N=100์ธ ๊ฒฝ์šฐ 60์ด์ƒ 100์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์†Œ์ˆ˜๋Š” 61, 67, 71, 73, 79, 83, 89, 97 ์ด 8๊ฐœ๊ฐ€ ์žˆ์œผ๋ฏ€๋กœ, ์ด๋“ค ์†Œ์ˆ˜์˜ ํ•ฉ์€ 620์ด๊ณ , ์ตœ์†Ÿ๊ฐ’์€ 61์ด ๋œ๋‹ค.

์ž…๋ ฅ

์ž…๋ ฅ์˜ ์ฒซ์งธ ์ค„์— M์ด, ๋‘˜์งธ ์ค„์— N์ด ์ฃผ์–ด์ง„๋‹ค.

M๊ณผ N์€ 10,000์ดํ•˜์˜ ์ž์—ฐ์ˆ˜์ด๋ฉฐ, M์€ N๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™๋‹ค.

์ถœ๋ ฅ

M์ด์ƒ N์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์†Œ์ˆ˜์ธ ๊ฒƒ์„ ๋ชจ๋‘ ์ฐพ์•„ ์ฒซ์งธ ์ค„์— ๊ทธ ํ•ฉ์„, ๋‘˜์งธ ์ค„์— ๊ทธ ์ค‘ ์ตœ์†Ÿ๊ฐ’์„ ์ถœ๋ ฅํ•œ๋‹ค. 

๋‹จ, M์ด์ƒ N์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ค‘ ์†Œ์ˆ˜๊ฐ€ ์—†์„ ๊ฒฝ์šฐ๋Š” ์ฒซ์งธ ์ค„์— -1์„ ์ถœ๋ ฅํ•œ๋‹ค.

ํ’€์ด

์ง€๋‚œ ์†Œ์ˆ˜ ๋ฌธ์ œ์™€ ๋น„์Šทํ•œ ๋ฌธ์ œ๋‹ค! 

#include <iostream>
#include <cmath>
using namespace std;

int main(){
    int M, N, sum=0, min=10000;
    bool isPrime = true;
    cin >> M >> N;

    for (int i=M; i<=N; i++){
      // 1์ธ ๊ฒฝ์šฐ
      if (i==1){
        isPrime = false;
      }
      else{
        for (int j=2; j<=sqrt(i); j++){
          if (i%j==0){
            isPrime = false;
            break;
          }
        }
      }
      // ์†Œ์ˆ˜์ธ ๊ฒฝ์šฐ
      if (isPrime == true){
        if (min > i){
          min = i;
        }
        sum += i;
      }
      isPrime = true;
    }
  
    if (sum == 0)
      cout << -1 << endl;
    else{
      cout << sum << endl;
      cout << min << endl;
    }
}

i๋ฅผ ์“ธ ์ž๋ฆฌ์— ์ž๊พธ M์„ ๋„ฃ์–ด์„œ ์•ˆ ๋Œ์•„๊ฐ”๋˜ ๋ฌธ์ œ. ๋ณ€์ˆ˜ ์‚ฌ์šฉ์— ์ฃผ์˜ํ•˜์ž

๋Œ“๊ธ€