스키마에듀 02/25 수업 백준 3문제

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

1929번: 소수 구하기

 

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

27433번: 팩토리얼 2

 

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

10871번: X보다 작은 수

 

에라토스테네스의 체 //1929번 소수 구하기

  굉장히 쉬운 문제인줄 알았으나, '시간 초과'에 걸려버리고 다시 푼 문제입니다. 지금까지 해왔던 방식대로 소수인가를 검증하면 시간 초과에 걸리게 됩니다. N의 최댓값은 1,000,000이기에, 만약 M=1, N=1,000,000이라면 그 사이에 있는 모든 수들을 하나씩 검증해야하고, 그렇게 하는데 많은 시간이 걸립니다. 시간을 줄이기 위해, '에라토스테네스의 체'라는 방법을 이용합니다. 이 방법을 잘 모르는 분들은 아래 GIF를 참고해주세요. 2를 소수로 표시한 후 모든 2의 배수를 지우고, 3을 소수로 표시한 후 모든 3의 배수를 지우고, ... 반복하여 특정 구간의 모든 소수를 구하는 방법입니다.

 

  보통 에라토스테네스의 체는 2부터 시작을 하지만, 이 문제에서는 시간을 더욱 줄이기 위해 M부터 시작합니다. 그렇다고 해서 M을 소수로 표시하고 지우는 것은 물론 아니고, 2부터 시작하여 오름차순으로 소수들의 배수를 지워줍니다. 이 과정을 최대 수인 N의 제곱근까지 반복하며, 제곱근이 정수가 아닐 경우에는 그 제곱근의 정수 부분까지 반복합니다.

  이러한 에라토스테네스의 체를 구현한 것이 위의 소스 코드입니다. 소수들의 배열 'prime_numbers'를 필요한 구간만큼 선언한 후, 필요한 구간의 숫자들로 초기화합니다. 그 후, 에라토스테네스의 체로 소수들을 하나씩 걸러주며, 만약 소수라면 그대로 두고 소수가 아니라면 배열에서 그 수를 0으로 바꿉니다. 0으로 바꾸는 것이 '지우는' 과정이므로, 이후의 검사들에서는 배제해도 괜찮습니다. 이러한 과정을 통해 얻게 되는 최종적인 'prime_numbers'에는 소수들만 남게 되고, 소수가 아닌 수들은 모두 0으로 치환됩니다.

//1929번 소수 구하기
#include <stdio.h>
#include <math.h>
int main(void) {
	
	int m, n, i, j;
	
	scanf("%d %d", &m, &n);
	int prime_numbers[n-m+1];
	
	for(i=0;i<(n-m+1);i++){
		prime_numbers[i] = i+m;
	}
	
	if(prime_numbers[0]==1){
		//1은 소수가 아니므로 1일 경우 0으로 바꿔준다. 
		prime_numbers[0]=0;
	}
	
	
	int max_num = (int)sqrt((float)n);
	
	for(i=2;i<=max_num;i++){
		for(j=0;j<(n-m+1);j++){
			if(prime_numbers[j]!=0){
				
				
				if(prime_numbers[j]==i){
					continue;
				}
				
				if(prime_numbers[j]%i==0){
					prime_numbers[j]=0;
				}
			}
		}
	}
	

	
	for(i=0;i<(n-m+1);i++){
		if(prime_numbers[i]!=0){
			printf("%d\n",prime_numbers[i]);
		}
	}
	
	return 0;
}

 

//팩토리얼 2 
#include <stdio.h>

double fact(int n){
	if (n==0 || n==1){
		return 1;
	}
	return n*fact(n-1);
}

int main(void){
	int n;
	scanf("%d",&n);

	printf("%.0lf",fact(n));
	
	return 0;
}

 

//X보다 작은 수 

#include <stdio.h>

int main(void){
	int n, x;
	scanf("%d %d",&n, &x);
	int arr[n];
	int i;
	
	for(i=0;i<n;i++){
		scanf("%d",&arr[i]);
		if(arr[i]<x){
			printf("%d ",arr[i]);
		}
	}

	return 0;
}