소수_알고리즘 기본편

소수

bool prime(int x){
	if(x<2){
		return false;
	}
	for (int i=2; i<=x+1; i++){
		if (x%i==0){
			return false;
		}
	}
	return true;
}

• 대략 이렇게 구현하면 O(N)정도의 시간 복잡도를 가짐
• 좀더 개선한 방법

bool prime(int x){
	if(x<2){
		return false;
	}
	for (int i=2;i<=x/2;i++){
		if(x%i==0{
			return false;
		}
	}
	return true;
}

• 위와 같이 하는 이유는 N이 2보다 크거나 같고,
• N/2보다 작거나 같은 자연수로 나눠 떨어지면 안되기때문에
• 즉, N = a * b로 나타낼 수 있는데 a가 작을 수록 b는 큼
  • 가능한 a중에서 가장 작은 값 2이기 때문에 b는 N/2를 넘지 않는 것
• 대략 시간 복잡도 O(N/2)하지만 커질수록 1/2는 의미 없어서 아직도 O(N)에 가깝다고 말할 수 있음
• 더더 빠른 방법

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

• N이 소수가 되려면 2보다 크거나 같고, 루트 N보다 작거나 같은 자연수로 나누어 떨어지면 안됨
  • N이 소수가 아니라면, N = a*b로 나타낼수 있음
    • a>b라면 두수를 바꿔서 항상 a≤b로 만들 수 있음
    • 두 수 a와 b 차이가 가장 작은 경우 루트 N임
    • 따라서 루트N까지만 검사해보면 됨
  • 시간 복잡도 대략 O(√N)
    • 이경우 이전 방식보다 1억까지 검사한다면 1만정도 까지 줄어 들 수 있음
• 왜 루트인데 저렇게 표현하나 하면
  • 컴퓨터에서 실수는 근사값을 나타내므로
    • √i ≤ N은
      • i ≤ N * N과 같기 때문에 저렇게 표시

문제 풀이_1978_소수 찾기

• 문제 링크
  • https://www.acmicpc.net/problem/1978
• 주어진 수들중 소수의 개수를 출력하면됨
• 소스 코드

#include<stdio.h>
#include<iostream>
using namespace std;
bool isPrime(int number) {
	if (number < 2) return false;
	for (int i = 2; i*i <= number; i++) {
		if (number%i == 0)
			return false;
	}
	return true;
}
int main(void) {
	int N;
	int ret=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int number;
		cin >> number;
		if (isPrime(number)) {
			ret++;
		}
	}
	cout << ret << '\\n';
	return 0;
}