소수의 굴레 BOJ 1978,1929, 2581

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

1929번: 소수 구하기

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

1978번: 소수 찾기

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

2581번: 소수

 

 

나는 항상 소수 문제를 풀어본 적은 많으나 풀 때마다 어떻게 풀었는지 기억이 안 나서 결국 못 풀고 답을 보는 경우가 많았다.  

답답해서 소수의 굴레에 들어왔다. 많은 문제를 푼 건 아니지만 이번 기회를 통해 확실히 알기 위해서 이 글을 쓴다.

(푼 지가 너무 오래돼서 기억이 날지 모르겠다.)

일단 가장 먼저 풀었던 1978부터 보겠다.

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

#include<iostream>

using namespace std;

int n, num, result,prime;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		result = 0;
		cin >> num;
		if (num != 2) {
			for (int j = 1; j<= num; j++) {
				if (num % j == 0) result++;
			}
			if (result == 2) prime++;
		}
		else if (num == 2) prime++;
		
	}
	cout << prime;
}

입력이 n개 들어왔을 때 그 n개의 숫자 중 소수는 몇 개인지 찾는 문제다.

num이라는 변수를 통해 숫자를 받는다. 

num이라는 수는 1부터 num까지 수로 나눠 나머지가 0인게 두 개 있을 때 소수로 판정하게 된다.

 

+ 어차피 소수는 약수가 1과 자신이기 때문에 for문 처음 시작을 1이 아니라 2부터 시작하고 result가 0일 때 출력해주면 된다. 

지금 다시 보니 브루트포스와 같은 유형이건가 싶기도하다.. 아닐 수도 있고..ㅎ 

 

다음은 1929이다.

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

 1978을 풀어봐서 쉬울 줄 알았다. 

아니었다.. 시간초과가 나서 너무 화가났다.. 이런건 잘 모르겠다. 

그래서 백준이 틀린 줄 알고 계속 좀 찾아보면서 제출했는데 .. ㅋ 내가 틀렸당.

 

첫 번째 제출은 

#include<iostream>

using namespace std;

int s, d, result;

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);

	cin >> s >> d;
	for (int i = s; i < d+1; i++) {
		result = 0;
		for (int j = 1; j <= i; j++) {
			if (i % j == 0) result++;
		}
		if (result == 2) cout << i<<"\n";
	}
}

 이거였다.. 

s부터 d까지의 수 중 소수인 것을 출력하는 문제였다. 

위의 문제처럼 풀었는데.. 안 됐다. 

d+1 - s 번 반복문을 돌리는데 그 반복문 안의 두 번째 반복문 안에서 소수를 판정하게 했다.

i는 s부터 d까지의 수,  j는 1부터 i까지 수를 의미하는데 i를 j로 나눠서 나머지가 0이 되는 값이 두 개일 때 소수로 판정했다. 

 

하지만.. 그렇게 되지 않았다.

 1 ≤ s ≤ d ≤ 1,000,000 가 문제에서 주어진 범위이다. 

만약 s와 d가 각각 1, 1,000,000라고 했을때 

첫번째 for문에서 999999번 연산하고 두번째 for문에서 똑같이 999999번 연산을 하게 될 것이다.

따라서 2억번 이상 연산하게 되므로 시간 초과가 나버리는 것이다.

 

두번째 풀이는 

#include<iostream>

using namespace std;

int s, d, result;

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);

	cin >> s >> d;
	
	for (int i = s; i< d+1; i++) {
		
		result = 0;
		for (int j = 1; j*j<= i; j++) {
			if (i % j == 0) result++;
			if (result == 2) break;
		}
		if (result == 1) cout << i<<"\n";
	}
}

 

 이번 코드는 두번째 for문에서 연산을 좀 줄일 수 있었다. 

j*j로 연산을 줄인 것인데,

이해한게 맞는지 잘 모르겠지만 우리가 약수를 구할 때를 생각하면서 이해를 했다. 

만약 12의 약수를 구한다고 할 때,

 

이렇게 구하는 것 처럼 여섯 번 다 도는게 아니라 3까지만 돌면 구할 수 있다. 

그런 것 처럼 어떤 수(n)의 소수를 구할 때 n의 반 까지만 돌면 소수를 판단할 수 있는게 아닐까..? ㅎ

 

근데 어쨌든 이 코드도 틀렸다.

1을 생각을 못했었다. 1 12 를 입력으로 받았을 때 소수에 1도 출력한다... 바보자식

 

최종코드는

#include<iostream>

using namespace std;

int s, d, result;

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);

	cin >> s >> d;
	if (s == 1) s = 2;
	for (int i = s; i< d+1; i++) {
		
		result = 0;
		for (int j = 1; j*j<= i; j++) {
			if (i % j == 0) result++;
			if (result == 2) break;
		}
		if (result == 1) cout << i<<"\n";
	}
}

s가 1일 때 2로 바꿔주는 코드를 작성했다.

위에 말했던 것 처럼 반만 계산하기 때문에 나머지가 0인게 1개이기만하면 소수가 된다.

만약 두개가 되어버리면 소수가 아니기 때문에 break를 시켜준다.

 

마지막 2581이다. 

이것도 쉽게 풀 수 있을 줄 알았는데 그러진 못했던 것 같다.

문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

#include<iostream>
#include<vector>
using namespace std;

vector<int>a;

int m, n, sum,result;

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);

	cin >> m>>n;
	
	if (m == 1) m = 2;
	for (int i = m; i <= n; i++) {
		int count = 0;
		for (int j = 1; j * j <= i; j++) {
			if (i % j == 0) count++;
			if (count == 2)  break;
		}
		if (count == 1) {
			a.push_back(i);
			sum += i;
		}
		
			
	}
	if (a.empty()) {
		cout << "-1";
	}
	else {
		cout << sum << "\n" << *(a.begin());
	
	}
}

소수 구하는 것은 위와 같다.

하지만 합과 가장 작은 것을 구해야하기 때문에 벡터를 사용해줬다. 

사실 배열을 써도 됐지만 벡터를 쓰고 싶어서 썼다. ㅎ

 

배열에 소수인 값을 넣고 sum 값에 계속 해서 더해줬다.

그리고 a.begin()은 벡터의 처음 값을 반환하는데 이는 a[0]로 고쳐줘도 무방하다.

 

 

++배열을 사용하지 않고 그냥 첫번째 값만 따로 저장해도 되는거였다..

 

이로써 나의 소수문제는 조금 풀 수 있게 되었다. 
하지만 에라토스테네스의 체라는 관문.. 남아있다. 
공부하게 되면 또 올리겠다.
 
잘못된 사실이 있다면 댓글로 알려주세요ㅎ.