[수학] 소수(2581), 약수 구하기(2501)

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

2581번: 소수

 

1. 문제 개요

 

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

 

2. 전체코드

#include<iostream>

using namespace std;

bool isPrime(int num) {
    if(num<2)
        return false;
    
    for(int i=2;i*i<=num;i++)
        if(num%i==0)
            return false;
    
    return true;
}

int main(void) {
    int startN, endN, sum=0;
    int firstPrime = -1;
    
    cin >> startN >> endN;
    
    for(int i=startN;i<=endN;i++) {
        if(isPrime(i)) {
            sum += i;
            if(firstPrime==-1)
                firstPrime = i;
        }
    }
    
    if(firstPrime==-1)
        cout << "-1" << endl;
    else
        cout << sum << endl << firstPrime << endl;
}

 

 

---

 

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

2501번: 약수 구하기

 

1. 문제 개요

 

두 개의 자연수 N과 K가 주어졌을 때, N의 약수들 중 K번째로 작은 수를 출력하는 프로그램을 작성하시오.

 

2. 전체 코드

#include<iostream>

using namespace std;

int main(void)
{
    int N, K, idx=0;
    scanf("%d%d",&N,&K);
    
    for(int i=1;i<=N;i++){
        if(N%i==0) idx++;
        if(idx==K){
            printf("%d",i);
            break;
        }
    }
    if(idx<K) printf("0");
}