소수 찾기 및 판별_심화
본문 바로가기
알고리즘 최종 (단계별)/1.수학

소수 찾기 및 판별_심화

by KyeongMin 2023. 7. 5.
728x90
반응형

에라토스테네스의 체

  • 2부터 N까지의 수를 써놓고
  • 지워지지 않은 수중에 가장 작은 수를 찾음
  • 그수를 지우고 소수로 저장
  • 그리고 그 수의 배수를 모두 지움
  • 지워지지 않은 수 중에서 가장 작은 수 는 2이고
  • 2는 소수이고 2의 배수를 모두 지움
  • 그리고 3의 배수를 지움
  • 5의 배수를 지운다.
  • 7의 배수를 지운다.
  • 그리고 11배수를 지우려고 하는데 이미 다 지워져 있고,
  • 2,3,5,7로 인해서
  • 11 * 11은 121로 100이 넘어서 더이상 수행 할 필요 없음
  • 그럼 남아있는 모든 수가 소수이다.

문제 풀이

#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];//ture: 지워짐, false : 지워지지 않음
int m, n;

int main() {
	check[0] = check[1] = true;
	for (int i = 2; i*i <= MAX; i++) {
		if (check[i] == false) {
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	 cin >> m>> n;
	for (int i = m; i <= n; i++) {
		if (check[i] == false) {
			cout << i << '\\n';
		}
	}
	return 0;
}

골드바흐의 추측

  • 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능
  • 위의 문장에 3을 더하면
  • 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능
  • 10^18이하 에서는 참인 것으로 증명됨
7 = 3 + 4 = 3 + 2 + 2
9 = 3 + 6 = 3 + 3 + 3
11 = 3 + 8 = 3 + 3 + 5
13 = 3 + 10 = 3 + 5 + 5
15 = 3 + 12 = 3 + 5 + 7
  • 문제 링크
  • 문제 풀이
    • 골드바흐의 추측으로 푼다.
    • 백만 이하의 짝수에 대해서 골드 바흐의 추측을 검증하는 문제
  • 소스코드
#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];
int m, n;
int prime[MAX];
int pn;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	check[0] = check[1] = true;
	for (int i = 2; i*i <= MAX; i++) {
		if (check[i] == false) {
			prime[pn++] = i;
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	while (1) {
		cin >> n;
		if (n == 0)break;
	
		for(int i=1;i<pn;i++){
			if (check[n - prime[i]] == false) {
				cout << n << " = " << prime[i] << " + " << n - prime[i] << "\\n";
				break;
			}
		}
	}
	return 0;
}
  • 소스에 대해서 소수를 뺀것들의 합이 소수이면 되는것이므로 위와 같이 구현하면됨

*번외

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);: 입/출력이 일어날때마다 C++ 스트림과 C 스트림을 동기화 시킵니다.

C++ 스트림은 대표적으로 cin, cout, cerr이 있고 C 스트림은 stdin, stdout, stderr이 있습니다.

동기화를 시키지 않으면 cin의 속도가 매우 빨라지게 되어서 시간 초과를 해결하는 경우가 많습니다.

이걸 사용한 경우에는 cin/cout과 scanf/printf를 섞어서 사용하면 올바른 입/출력을 받을 수 없습니다.

자세한 내용은 <https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio> 에서 찾아보세요.

밑의 두개는 여기서 설명하기 보다는 직접 찾아보는 것이 좋을 것 같습니다.

심화 소수 찾기 및 판별

에라토스테네스의 체

  • 2부터 N까지의 수를 써놓고
  • 지워지지 않은 수중에 가장 작은 수를 찾음
  • 그수를 지우고 소수로 저장
  • 그리고 그 수의 배수를 모두 지움
  • 지워지지 않은 수 중에서 가장 작은 수 는 2이고
  • 2는 소수이고 2의 배수를 모두 지움

  • 그리고 3의 배수를 지움

  • 5의 배수를 지운다.

  • 7의 배수를 지운다.

  • 그리고 11배수를 지우려고 하는데 이미 다 지워져 있고,
  • 2,3,5,7로 인해서
  • 11 * 11은 121로 100이 넘어서 더이상 수행 할 필요 없음
  • 그럼 남아있는 모든 수가 소수이다.

문제 풀이

#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];//ture: 지워짐, false : 지워지지 않음
int m, n;

int main() {
	check[0] = check[1] = true;
	for (int i = 2; i*i <= MAX; i++) {
		if (check[i] == false) {
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	 cin >> m>> n;
	for (int i = m; i <= n; i++) {
		if (check[i] == false) {
			cout << i << '\\n';
		}
	}
	return 0;
}

골드바흐의 추측

  • 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능
  • 위의 문장에 3을 더하면
  • 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능
  • 10^18이하 에서는 참인 것으로 증명됨
7 = 3 + 4 = 3 + 2 + 2
9 = 3 + 6 = 3 + 3 + 3
11 = 3 + 8 = 3 + 3 + 5
13 = 3 + 10 = 3 + 5 + 5
15 = 3 + 12 = 3 + 5 + 7
  • 문제 링크
  • 문제 풀이
    • 골드바흐의 추측으로 푼다.
    • 백만 이하의 짝수에 대해서 골드 바흐의 추측을 검증하는 문제
  • 소스코드
#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];
int m, n;
int prime[MAX];
int pn;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	check[0] = check[1] = true;
	for (int i = 2; i*i <= MAX; i++) {
		if (check[i] == false) {
			prime[pn++] = i;
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	while (1) {
		cin >> n;
		if (n == 0)break;
	
		for(int i=1;i<pn;i++){
			if (check[n - prime[i]] == false) {
				cout << n << " = " << prime[i] << " + " << n - prime[i] << "\\n";
				break;
			}
		}
	}
	return 0;
}
  • 소스에 대해서 소수를 뺀것들의 합이 소수이면 되는것이므로 위와 같이 구현하면됨

*번외

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);: 입/출력이 일어날때마다 C++ 스트림과 C 스트림을 동기화 시킵니다.

C++ 스트림은 대표적으로 cin, cout, cerr이 있고 C 스트림은 stdin, stdout, stderr이 있습니다.

동기화를 시키지 않으면 cin의 속도가 매우 빨라지게 되어서 시간 초과를 해결하는 경우가 많습니다.

이걸 사용한 경우에는 cin/cout과 scanf/printf를 섞어서 사용하면 올바른 입/출력을 받을 수 없습니다.

자세한 내용은 <https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio> 에서 찾아보세요.

밑의 두개는 여기서 설명하기 보다는 직접 찾아보는 것이 좋을 것 같습니다.

심화 소수 찾기 및 판별

에라토스테네스의 체

  • 2부터 N까지의 수를 써놓고
  • 지워지지 않은 수중에 가장 작은 수를 찾음
  • 그수를 지우고 소수로 저장
  • 그리고 그 수의 배수를 모두 지움
  • 지워지지 않은 수 중에서 가장 작은 수 는 2이고
  • 2는 소수이고 2의 배수를 모두 지움
  • 그리고 3의 배수를 지움
  • 5의 배수를 지운다.
  • 7의 배수를 지운다.
  • 그리고 11배수를 지우려고 하는데 이미 다 지워져 있고,
  • 2,3,5,7로 인해서
  • 11 * 11은 121로 100이 넘어서 더이상 수행 할 필요 없음
  • 그럼 남아있는 모든 수가 소수이다.

문제 풀이

#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];//ture: 지워짐, false : 지워지지 않음
int m, n;

int main() {
	check[0] = check[1] = true;
	for (int i = 2; i*i <= MAX; i++) {
		if (check[i] == false) {
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	 cin >> m>> n;
	for (int i = m; i <= n; i++) {
		if (check[i] == false) {
			cout << i << '\\n';
		}
	}
	return 0;
}

골드바흐의 추측

  • 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능
  • 위의 문장에 3을 더하면
  • 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능
  • 10^18이하 에서는 참인 것으로 증명됨
7 = 3 + 4 = 3 + 2 + 2
9 = 3 + 6 = 3 + 3 + 3
11 = 3 + 8 = 3 + 3 + 5
13 = 3 + 10 = 3 + 5 + 5
15 = 3 + 12 = 3 + 5 + 7
  • 문제 링크
  • 문제 풀이
    • 골드바흐의 추측으로 푼다.
    • 백만 이하의 짝수에 대해서 골드 바흐의 추측을 검증하는 문제
  • 소스코드
#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];
int m, n;
int prime[MAX];
int pn;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	check[0] = check[1] = true;
	for (int i = 2; i*i <= MAX; i++) {
		if (check[i] == false) {
			prime[pn++] = i;
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	while (1) {
		cin >> n;
		if (n == 0)break;
	
		for(int i=1;i<pn;i++){
			if (check[n - prime[i]] == false) {
				cout << n << " = " << prime[i] << " + " << n - prime[i] << "\\n";
				break;
			}
		}
	}
	return 0;
}
  • 소스에 대해서 소수를 뺀것들의 합이 소수이면 되는것이므로 위와 같이 구현하면됨

*번외

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);: 입/출력이 일어날때마다 C++ 스트림과 C 스트림을 동기화 시킵니다.

C++ 스트림은 대표적으로 cin, cout, cerr이 있고 C 스트림은 stdin, stdout, stderr이 있습니다.

동기화를 시키지 않으면 cin의 속도가 매우 빨라지게 되어서 시간 초과를 해결하는 경우가 많습니다.

이걸 사용한 경우에는 cin/cout과 scanf/printf를 섞어서 사용하면 올바른 입/출력을 받을 수 없습니다.

자세한 내용은 <https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio> 에서 찾아보세요.

밑의 두개는 여기서 설명하기 보다는 직접 찾아보는 것이 좋을 것 같습니다.

심화 소수 찾기 및 판별

에라토스테네스의 체

  • 2부터 N까지의 수를 써놓고
  • 지워지지 않은 수중에 가장 작은 수를 찾음
  • 그수를 지우고 소수로 저장
  • 그리고 그 수의 배수를 모두 지움
  • 지워지지 않은 수 중에서 가장 작은 수 는 2이고
  • 2는 소수이고 2의 배수를 모두 지움
  • 그리고 3의 배수를 지움
  • 5의 배수를 지운다.
  • 7의 배수를 지운다.
  • 그리고 11배수를 지우려고 하는데 이미 다 지워져 있고,
  • 2,3,5,7로 인해서
  • 11 * 11은 121로 100이 넘어서 더이상 수행 할 필요 없음
  • 그럼 남아있는 모든 수가 소수이다.

문제 풀이

#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];//ture: 지워짐, false : 지워지지 않음
int m, n;

int main() {
	check[0] = check[1] = true;
	for (int i = 2; i*i <= MAX; i++) {
		if (check[i] == false) {
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	 cin >> m>> n;
	for (int i = m; i <= n; i++) {
		if (check[i] == false) {
			cout << i << '\\n';
		}
	}
	return 0;
}

골드바흐의 추측

  • 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능
  • 위의 문장에 3을 더하면
  • 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능
  • 10^18이하 에서는 참인 것으로 증명됨
7 = 3 + 4 = 3 + 2 + 2
9 = 3 + 6 = 3 + 3 + 3
11 = 3 + 8 = 3 + 3 + 5
13 = 3 + 10 = 3 + 5 + 5
15 = 3 + 12 = 3 + 5 + 7
  • 문제 링크
  • 문제 풀이
    • 골드바흐의 추측으로 푼다.
    • 백만 이하의 짝수에 대해서 골드 바흐의 추측을 검증하는 문제
  • 소스코드
#include<stdio.h>
#include<iostream>
using namespace std;
const int MAX = 1000000;
bool check[MAX + 1];
int m, n;
int prime[MAX];
int pn;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	check[0] = check[1] = true;
	for (int i = 2; i*i <= MAX; i++) {
		if (check[i] == false) {
			prime[pn++] = i;
			for (int j = i + i; j <= MAX; j += i) {
				check[j] = true;
			}
		}
	}

	while (1) {
		cin >> n;
		if (n == 0)break;
	
		for(int i=1;i<pn;i++){
			if (check[n - prime[i]] == false) {
				cout << n << " = " << prime[i] << " + " << n - prime[i] << "\\n";
				break;
			}
		}
	}
	return 0;
}
  • 소스에 대해서 소수를 뺀것들의 합이 소수이면 되는것이므로 위와 같이 구현하면됨

*번외

ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);: 입/출력이 일어날때마다 C++ 스트림과 C 스트림을 동기화 시킵니다.

C++ 스트림은 대표적으로 cin, cout, cerr이 있고 C 스트림은 stdin, stdout, stderr이 있습니다.

동기화를 시키지 않으면 cin의 속도가 매우 빨라지게 되어서 시간 초과를 해결하는 경우가 많습니다.

이걸 사용한 경우에는 cin/cout과 scanf/printf를 섞어서 사용하면 올바른 입/출력을 받을 수 없습니다.

자세한 내용은 <https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio> 에서 찾아보세요.

밑의 두개는 여기서 설명하기 보다는 직접 찾아보는 것이 좋을 것 같습니다.
728x90
반응형

'알고리즘 최종 (단계별) > 1.수학' 카테고리의 다른 글

수학2_a^b에대해서 알아보자.  (0) 2023.07.12
소인수분해와 팩토리얼_알고리즘  (0) 2023.07.08
소수_알고리즘 기본편  (0) 2023.07.04
진법 변환 - 심화  (0) 2023.06.28
진번 기초 문제  (0) 2023.06.27

관련글

댓글

티스토리툴바