15. 소수의 개수

    15번 문제   

 

 

    내가 풀이한 답   

  마땅한 방법이 떠오르지 않아 일반적인 순회(for)를 두 번 돌아 모든 경우의 수를 다 접근하며 소수를 판별하는 식으로 작성하였다.  

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	

	int n, i, j, cnt = 0;
	bool flag;
	scanf("%d", &n);
	
	for(i=2; i<=n; i++){
		flag = true;
		for(j=2; j<i; j++){
			if(i%j==0){
				flag = false;
				break;
			}
		}
		if(flag==true) cnt++;
	}
	
	printf("%d", cnt);
	return 0;
}

 

 결과는 예상대로 시간초과가 났다. 

 

 

 곰곰히 생각해봤지만 마땅한 답이 떠오르지 않아서 강의 도입부를 참조했다. 시간 초과가 나는 이유의 대부분은 굳이 참조하지 않아도 될 경우의 수를 모두 접근했을 때 발생한다는 얘기를 들었다. 소수 판별에서도 소수라고 판단이 되는 경우의 수를 제곱근으로 줄일 수 있다. 밑에 예시처럼 36을 보면 나머지가 0이되는 경우의 수는 총 10개이지만 5개만 확인해도 소수판별이 가능하다는 이야기이다.  

 

 

    사이트의 답안   

 

#include <stdio.h>
using namespace std;

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	

	int n, i, j, cnt = 0;
	bool flag;
	scanf("%d", &n);
	
	for(i=2; i<=n; i++){
		flag = true;
		for(j=2; j*j<=i; j++){
			if(i%j==0){
				flag = false;
				break;
			}
		}
		if(flag==true) cnt++;
	}
	
	printf("%d", cnt);
	return 0;
}

 

12번째 줄 순회(for)문에서 제곱근(sqrt 함수) 대신 왼쪽에 j를 한번 더 곱해주었다. 그 결과 통과를 했다.

 

 

    조금 더 정리   

 

  소수 판별에 대해 좀 더 공부하고 싶어서 인터넷을 찾아보았다. 찾아보니 에라토스테네스의 체 라는 방법이 나왔다. 논리는 다음과 같다. 2부터 입력받은 수까지 for문을 돌며 각 소수의 배수들은 소수가 아니므로 다 제외시키는 방법이다. 

 

 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);	

	int n, i, j, cnt=0;
	scanf("%d", &n);
	int *arr = (int *)malloc(sizeof(int) * n);
	memset(arr, 0, n * sizeof(int));
	
	for(i=2; i<=n; i++){
		if(arr[i]==1) continue;
		for(j = i+i; j<=n; j+=i) arr[j] = 1;
	}
	
	for(i=2; i<=n; i++){
		if(arr[i]!=1) cnt++;
	}
	
	printf("%d", cnt);
	free(arr);
	return 0;
}