수학(소수판별)

정영훈·2022년 9월 3일

알고리즘

알고리즘기초

목록 보기

5/6

소수

🎉 정의

소수
- 1과 자기자신만으로 나누어지는 수
- 약수가 2개인 수
- 예) 3, 5, 7, 11
합성수
- 1과 자기자신을 제외한 다른 약수를 가지고 있는 수
- 예) 2, 4, 8, 10, 12

💻 소수 판별법

1과 자기자신으로만 나누어지는 수
약수가 2개인 수
2부터 N-1까지의 수로 나누어지지 않는 수

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n==1){ //n이 1이면 소수가 아님
        cout<<"Not Prime";
        return 0;
    }
    for(int i=2;i<n;i++){
        if(n%i==0){ //약수가 있다면 소수가 아님
            cout<<"Not Prime";
            return 0;
        }
    }
    cout<<"Prime"; //2부터 n-1까지 나누어 지지 않는 수가 있다면 소수
    return 0;
}

시간복잡도 : O(N)

백준 연습문제

😊 보다 효율적인 알고리즘

위와 같은 알고리즘을 이용하여 소수를 구할 때는 반복문을 사용하여 2부터 n-1까지의 수 중 나머지가 0이 되는 수가 존재하는 지 루프를 돌면서 판별할 수 있다.

하지만 이런 알고리즘은 비효율적으로 큰수일 경우 엄청난 반복을 하게 되어 시간 제한이 있는 알고리즘 문제에서는 시간초과가 걸릴 수 있다.

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

효율적인 알고리즘 - 제곱근을 활용한 반복 횟수 줄이기

시간 복잡도 : O(sqrt(n))
✔ sqrt는 제곱근을 구하는 함수 : sqrt(4) -> 2, sqrt(9) -> 3

어떤 자연수가 소수인지 계산 할 때 n-1까지 나눠 떨어지는지를 모두 확인할 필요가 없고 제곱근까지만 나눠봐도 소수임을 알 수 있다.
합성수 N에서 1을 제외한 가장 작은 약수는 N의 제곱근이다.
아래의 예시를 참고할 수 있다.

N	가장 작은 약수	$\sqrt{N}$
18	2	4.24..
21	3	4.58..
25	5	5
27	3	5.19..

N이 합성수 일때 N = A*B, 1<A,B<N이다. 만약 A,B가 둘 다 $\sqrt{N}$ 보다 크다면, N = $\sqrt{N}$ * $\sqrt{N}$ < A*B = N이 되어 모순이다. 따라서 A,B 중 하나는 $\sqrt{N}$ 보다 같거나 작다.

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    if(m==1){
        return 0;
    }

    for(int i=n;i<=m;i++){
        bool flag = true;
        if(i==1)continue;
        for(int j=2;j<=sqrt(i);j++){
            if(i%j==0){
                flag = false;
                break;
            }
        }
        if(flag){
            cout<<i<<'\n';
        }
    }
}

위의 알고리즘 보다 반복 횟수를 줄이려면 2를 제외한 모든 짝수는 소수가 아닌점을 활용할 수 있다.
짝수는 모두 합성수로 판별하고 나머지 홀수 중에서 제곱근을 활용하여 반복횟수를 줄일 수 있다.

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    if(m==1){
        return 0;
    }

    for(int i=n;i<=m;i++){
        bool flag = true;
        if(i==1)continue; //1은 소수가 아님
        if(i==2){ //2는 소수
            cout<<i<<'\n';
            continue;
        }
        else if(i%2==0){ //짝수면 합성수
            flag = false;
            continue;
        }
        for(int j=3;j*j<=i;j+=2){ //홀수는 제곱근까지 비교
            if(i%j==0){
                flag = false;
                break;
            }
        }
        if(flag){
            cout<<i<<'\n';
        }
    }
}

😁 보다 효율적인 알고리즘 - 에라토스테네스의 체

에라토스테네스의 체는 소수를 찾는 방법으로 고대 그리스 수학자 에라토스테네스가 발견했다.

👍 알고리즘

2부터 소수를 구하자고 하는 구간의 모든 수를 나열한다.
2는 소수이므로 소수로 출력하고, 2를 제외한 모든 2의 배수는 지운다.
3은 소수이므로 소수로 출력하고, 3을 제외한 모든 3의 배수는 지운다.
5는 소수이므로 소수로 출력하고, 5를 제외한 모든 5의 배수는 지운다.
7은 소수이므로 소수로 출력하고, 7를 제외한 모든 7의 배수는 지운다.
위 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    vector<bool> prime(m+1,true);
    prime[1]=false;
    for(int i=2;i*i<=m;i++){
    	if(prime[i]){
    		for(int j=i*i;j<=m;j+=i){
    			prime[j]=false;
			}
		}
	}
    for(int i=n;i<=m;i++){
    	if(prime[i]){
    		cout<<i<<'\n';
		}
	}
}