소수 구하기, 소인수분해

[ 소수 구하기 ]

 

1 ~ N까지 모든 소수를 구하기 - 에라토스테네스의 체

 

1. 1은 소수가 아니다. 2. 2부터 시작하여 아직 지워지지 않은 수는 소수이다. 3. 소수를 찾았으면, 그 수의 배수를 모두 지운다. 4. 루트 N까지만 검사를 해보면 된다.

 

Step 0. 초기상태. 1은 소수가 아니므로 지운다.

 

Step 1. 2부터 시작한다. 2는 지워지지 않았으므로 2는 소수이며 2의 배수를 모두 지운다.

 

 

Step 2. 그다음 수 3이 지워지지 않았으므로, 3도 소수이고, 3의 배수를 모두 지운다.

 

 

Step 3. 4는 이미 지워져있으므로, 소수가 아니다.

 

Step 4. 이런식으로 루트N까지 검사했을 때, 남아있는 수들이 모두 소수이다.

 

 

[ 소수 구하기 문제 ]

 

문제 링크 : https://www.acmicpc.net/problem/1929

 

M이상 N이하의 소수를 모두 구하는 문제이다.

 

#include <stdio.h> 
#define MAX_NUMBER 1000001 

bool checked[MAX_NUMBER] = { false, }; 

int main(void)
{
	int M, N; 
    scanf("%d %d", &M, &N); 
    checked[0] = checked[1] = true; 
    
    for (register int i = 2; i*i <= N; i++) 
    {
    	if (checked[i] == false) 
        { 
        	for (register int j = 2; i*j <= N; j++) 
            { 
            	checked[i*j] = true; 
            } 
        } 
     }
     
     for (register int i = M; i <= N; i++)
     {
     	if (checked[i] == false) 
        	printf("%d\n", i);
     }
     return 0;
}

 

---

 

[ 소인수분해 ]

 

- 정수 N을 소인수분해 할 때, 소인수의 가장 큰 값은 X^2의 형태일 것이므로 루트 N이 가장 큰 값이 된다.

 

- 2부터 루트 N까지 반복문을 돌면서, 어떤 수를 나눌 수 있을 경우 나눌 수 없을 때까지 나누면 된다.

 

- 다 나누고 남은 N이 1보다 클 경우는 그 수를 한번 더 출력해 준다.

(인수가 루트 N보다 크다는 얘기이다. 루트 N보다 큰 인수는 단 한번만 나오는 것이 보장되므로, 한번만 체크하여 출력하면 된다.)

 

 

[ 소인수분해 문제 ]

 

팩토리얼 0의 개수 성공   시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 7874 3417 2905 46.517% 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1  10 예제 출력 1  2

 

[ 문제 풀이 ]

 

- N팩토리얼에서 0의 개수가 몇개인지 출력하는 문제이다. 

- 10은 소인수 2와 5의 곱이므로, 2와 5의 개수 중 작은 개수가 10의 개수이다.

- 5의 개수가 2의 개수보다 작으므로 5의 개수만 세어주면 된다.

(팩토리얼이 아닌 조합에서 0의 개수를 구하려면, 뭐가 더 작을지 모르므로 2의 개수 및 5의 개수를 둘다 세어서 작은 개수로 판단 해야한다.)

 

- N! = 1 x 2 x ... x N 이다. 5의 개수를 세기 위해,

- 5로 나누어 떨어지는 수의 개수를 세어준다. (N / 5가 된다.)

- 그런데 25의 경우는 5 x 5로 표현되므로, 또 25로 나누어 떨어지는 수도 세어준다. (N / 25가 된다.)

- 이런식으로 5의 제곱꼴로 나눌 수 있다면, 그 수로 나누어 떨어지는 수의 개수를 또 따로 세어준다. 

 

 

[ 최종 구현(C++) ]

#include <stdio.h> 

int main(void)
{
	int N; 
    long long result = 0LL; 
    scanf("%d", &N); 
    for (int i = 5; i <= N; i *= 5)
    {
    	result += (long long)(N / i);
    }
    
    printf("%lld\n", result);
    return 0;
}