[c/c++] 백준 1978_소수 찾기

소수 찾기 문제

처음에는 간단하게 생각했는데 여러가지 방법이 있더라
평소에 하던 방법은 직접 입력된 수를 1부터 자기 자신까지 다 나누어 보면서 반복문을 돌렸다.

O(N)의 시간만큼 소요
이 방법을 사용한 사람들 코드를 보니 그렇게해도 시간 초과는 안되는듯? 그래도 시간 적게 돌리고 싶어서 고민

다른 방법으로는 자신의 루트 값까지 반복문을 돌리면서 나뉘어 지는지 확인

곱셈의 특성 상 약수가 짝지어 이루어지기 때문에 루트 아래로만 나뉘어 지는지 확인해도 자연스럽게 약수 판별이 가능

O(√N) 의 시간 복잡도를 가지며 시간이 반절로 줄어든다.

에라토스테네스의 체라는 소수 판별 알고리즘이 있었다. 이건 또 무슨 수학자람

시간복잡도 O(Nlog(logN))를 가지는데 증명 과정을 보니 패스하도록 하자.

출처 - 위키백과 에라토스테네스의 체

위처럼 일정 수 안의 값들에서 배수를 다 지우는 방식인데 120은 11의 제곱보다 작기때문에 11부터는 배수를 만들어 주지 않고 카운트를 시작해주면 된다.

그 이유는 위에서 말했던것과 같이 곱셈은 두 쌍의 약수를 가지기 때문에 더 찾아볼 필요가 없기 때문(이미 앞에서 다 체크)

#include <iostream>
using namespace std;

#define MAX 1001

void judge_PN(int *arr){
	
	for(int i=2; i*i<=MAX; i++){
		if(arr[i] == 1)
			continue;
		for(int j=i*i; j<MAX; j+=i)
			arr[j] = 1;	
	}
	
}

int main(){//백준 1978 소수찾기 
	
	int N;
	int PNarr[MAX] = {0, };
	
	scanf("%d", &N);
	
	int num[N];
	int count = 0;
	
	judge_PN(PNarr);
	PNarr[1] = 1;
	
	//for(int i=0; i<1000; i++) printf("%d ", PNarr[i]);
	
	
	for(int i=0; i<N; i++){
		int check = 0;
		scanf("%d", &check);
		if(PNarr[check] == 0)
			count++;
	}
	
	cout << count;
				
	return 0;
}

함수를 따로 구현해서 1000개의 수까지 모두 소수 판별.

소수가 아닌 수는 1로 변경 소 인 수는 그대로 0의 값 가짐.

1 예외 처리를 안해줘서 소수로 판별해가지구 왜 틀렸는지 찾는데 좀 걸렸네 바보인듯

함수 매개변수로 1차원 배열은 int *arr 형태의 정수형 포인터로 전달할 수 있지만 2차원 배열부터는 다르게 전달