백준 2581 소수 코드 포함

소수 Prime Number'

처음 소수를 판별하여 출력하라! 라고 한다면 소수의 정의를 따라간다.

소수는 1과 자기 자신을 약수로 갖는 값으로
1과 자기 자신외의 약수를 가지지 않는 1보다 큰 수라고 하는데 한번 꼬아놓은 말이라 개인적으로 싫어한다.
그냥 1보다 크고, 약수로 1과 자기 자신을 갖는 값이라고 직설적인 말을 쓰면 좋지 않을까?

하여튼 소수를 구하기 위해서는 자기 자신보다 작은 값들로 나누어서 나누어지면 안된다.
= 나누어진다는 것은 배수라는 의미이기 때문이다.

int number = 4;
bool isPrime = true;
for(int i=number-1; i>1; i++){
	if(number%i==0){
    	isPrime = false;
        break;
    }
 }

내가 가진 수를 for문으로 돌려 나누어진다면 소수가 아니란 것을 알 수 있다.

여기서 더 나아간다면 자기 자신의 값보다 작은 소수의 값으로 나누어보면 된다.

또 다른 방법은 에라토스테네스의 체로 구하는 방법도 있고 그 방법은 아래와 같다.

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

bool number[10001];

int main(){
    int m, n;
    cin >> m >> n;

    int count = ceil(sqrt(10000));
    for(int i=2; i<=count; i++){
        for(int j=i+i; j<=10000; j=j+i){
            number[j] = 1;
        }
    }

    int answer = 0, answer2 = 0;
    for(int i=m; i<=n; i++){
        if(i == 1) continue;
        if(number[i] == false){ answer += i; } 
        if(answer2 == 0 && number[i] == false) answer2 = i;
        
    }
    if(answer) cout << answer << '\n' << answer2;
    else cout << "-1";
}

그런데 또 다른 방법이 있다. 점화식으로도 구할 수 있다.

dl.dongascience.com/magazine/view/M201904N015

아래 링크에 들어가보면 2019년 미국수학회에서 발행한 수학 잡지에 소수 구하는 점화식에 대한 여구가 실려있다고 나와있고 이미지로 소수에 대한 점화식이 존재한다.와우!