반응형
DoZZang
Do IT
DoZZang
전체 방문자
오늘
어제
  • Programming
    • Git
    • Web
    • 기타
    • Python
      • CodeUp
    • Math
    • Algorithm
    • Baekjoon
    • C,C++
    • Life
      • 독서
      • Just
      • 영화

블로그 메뉴

  • 홈
  • 태그
  • 방명록

인기 글

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
DoZZang

Do IT

[C] 백준 2581번 : 소수
Baekjoon

[C] 백준 2581번 : 소수

2023. 1. 26. 18:50
반응형
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>

int isPrimeNumber(int x);			//소수 판별 함수 선언
int main() {
	int N, M, sum = 0, x = 0;
	int Prime[1230] = { 0 };	//10000이하의 소수는 1229개
	scanf("%d%d", &M, &N);
	for (int i = M; i <= N; i++) {
		sum += isPrimeNumber(i);
		if (isPrimeNumber(i) > 0) {
			Prime[x] = isPrimeNumber(i); 	//최소값 판별을 위해
			x++;
		}
	}

	int min = Prime[0];
		if (sum == 0) printf("-1");		//소수가 없을 시 -1 출력
		else printf("%d\n%d", sum, min);
	}


int isPrimeNumber(int x) {
	int length;
	length = sqrt(x);
	if (length == sqrt(x)) return 0;		//1을 배제하자
	for (int i = 2; i <= length; i++) {
		if (x % i == 0) return 0;
	}
	return x;
}

문제에서 요구한 것은 크게 3가지였다.

1.주어진 범위 내에 소수를 판별하고

2.그 판별한 소수들의 합을 구해라.

3.그 판별한 소수들의 최소값을 구해라.

소수를 판별하는게 가장 우선시되어야한다.

그 중 가장 효율적인 방법인 에라토스테네스의 체를 이용할 것인데

 

에라토스테네스의 체는

어떠한 숫자가 주어졌을 때 그 숫자의 제곱근 이하의 범위까지만 약수가 존재하는지 판별하면

그 숫자가 소수인지 아닌지 알 수 있게 해준다.

자세한 이유는 아래 링크에 기술되어있다.

https://developer-dz.tistory.com/5

 

[C] 소수 구하기 / 에라토스테네스의 체 / 소수 구하기 최적화 / 1000개의 소수 구하기 / 범위 내의

먼저 코드입니다. 선 코드 후 이해하도록 하겠습니다. 100이하의 소수찾기 (에라토스테네스의 체) #include int main(int argc,char *argv[]) { int number = 100; // 100이하의 소수 찾기 int arr[101] = {0}; // 2부터 100

developer-dz.tistory.com

 

소수의 판별이 완료되었다면 소수들의 합을 출력해야했다.

굳이 따로 변수에 초기화해줄 필요없이 sum 변수에 더해줬다.

 

최소값을 구해주는 과정은 바로 수행할 수 없다고 판단하여

Prime배열을 선언해주었는데 Prime배열의 크기는

문제에 나와있는 N,M이 10000이하의 자연수라 하였기 때문에

10000은 1229개의 소수를 가지고 있어 1230으로 크기를 선언해주었다.

 

1978번 : 소수 찾기를 선행하여 풀어봤다면 큰 문제 없이 풀 수 있는 문제였다.

반응형
저작자표시 (새창열림)

'Baekjoon' 카테고리의 다른 글

[C] 백준 1929번 : 소수 구하기  (0) 2023.01.27
[C] 백준 11653번 : 소인수분해  (0) 2023.01.27
[C] 백준 1978번 : 소수 찾기  (0) 2023.01.26
[C] 백준 2839번 : 설탕 배달  (0) 2023.01.25
[C]백준 1316번 : 그룹 단어 체커  (0) 2023.01.25
    'Baekjoon' 카테고리의 다른 글
    • [C] 백준 1929번 : 소수 구하기
    • [C] 백준 11653번 : 소인수분해
    • [C] 백준 1978번 : 소수 찾기
    • [C] 백준 2839번 : 설탕 배달
    DoZZang
    DoZZang
    과정은 힘들지만 성장은 즐겁습니다.

    티스토리툴바