C언어 9주차

#include <stdio.h>
#include <stdbool.h>

#define max 100000

int arr[max + 1];  // 소인수를 저장할 배열

void min(int N) {
    for (int i = 2; i <= N; i++) {
        if (arr[i] == 0) {  
            arr[i] = i;  
            for (int j = i * 2; j <= N; j += i) {
                if (arr[j] == 0) {
                    arr[j] = i; 
                }
            }
        }
    }
}

int large(int num) {
    int max_P = arr[num];  
    while (num != 1) {
        max_P = (arr[num] > max_P) ? arr[num] : max_P;  
        num /= arr[num]; 
    }
    return max_P;
}

int main() {
    int N, K;
    scanf("%d %d", &N, &K);  
    
    min(N);  
    
    int count = 0;
    
    for (int i = 1; i <= N; i++) {
        if (large(i) <= K) {  
            count++;
        }
    }
    
    printf("%d\n", count); 
    
    return 0;
}

 

1.N, K에 해당하는 값을 입력받고 arr로 소인수를 저장할 배열을 만듭니다. 

2. min함수에서 각 숫자들의 최소 소인수들을 저장합니다. 이때 사용되는 건 에라토스테네스의 체라는 알고리즘이라고 합니다.

3. large함수로 각 숫자들을 입력받은 K보다 작은지 큰지 비교합니다. 

3-1.k보다 작을 경우 count값이 증가하게 됩니다. 

4.출력합니다.

 

#include <stdio.h>

int arr[301][301];
int cum[301][301];

void cum_sum(int N, int M){
	for(int i = 1; i <=N; i++){
    	for(int j = 1; j<=M; j++){
        	cum[i][j] = arr[i][j] + cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1];
        }
    }
}

int term_sum(int i, int j, int x, int y){
	return cum[x][y] - cum[i-1][y] - cum[x][j-1] + cum[i-1][j-1];
}

int main(){
	int N, M;
    scanf("%d %d", &N, &M);
    
    for(int i =  1; i<= N; i++){
    	for(int j = 1; j <=M; j++){
        	scanf("%d", &arr[i][j]);
        }
}

cum_sum(N, M);

int K;
scanf("%d", &K);

for(int k = 0; k < K; k++){
	int i, j, x, y;
    scanf("%d %d %d %d", &i, &j, &x, &y);
    printf("%d\n", term_sum(i, j, x, y));
}

return 0;

}

 

1.코드 가장 윗부분에 입력된 배열과 누적된 합을 받을 배열을 따로 만들어준다. 

2.cum_sum함수에서 각 원소를 누적합 방식으로 계산하여 cum에 저장해준다. 

3.term_sum에서는 (i,j)부터 (x, y)까지의 합을 구해줍니다. 

3-1.이때 cum을 사용해줍니다. 

4. 각 결과에 대해 구한 합을 출력해준다.