소수 문제

종류

소수 문제는 기본적으로 그냥 범위내에서 소수의 갯수를 구하는 문제와 어떤 소수가 있는지를 구하는 문제로 나뉜다.

소수의 갯수를 구하는 유형

1978 소수찾기

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#define len 1001
using namespace std;

bool go(int a) {
	if (a < 2) return 0;
	else {
		for (int i = 2; i * i <= a; i++) {
			if (a % i == 0) return 0;
		}
	}
	return 1;
}

int main(void) {
	
	freopen("input.txt", "r", stdin);

	int t;
	cin >> t;
	int ans = 0;
	while (t--) {
		int tmp;
		cin >> tmp;
		ans += go(tmp);
	}

	cout << ans << '\n';
}

보통은 위와 같은 방식으로 푸는데 이것도 속도 제한에 심하게 걸리는 편이다.

그래서 나온것이 에라토스테네스의 체이다.

1929 소수구하기

그래서 에라토스테네스의 체가 뭐냐하면 2부터 시작해서 관련 배수 다 지우고 3부터 시작해서 관련 배수 다 지우는 그러다 보면 남은 것은 모두 소수라는 알고리즘이다.

#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstring>
#include <cstdio>
#include <functional>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <ctime>
#define len 1001
using namespace std;

int main(void) {
	
	freopen("input.txt", "r", stdin);

	bool num[1000001] = { 0 };

	num[1] = true;
	for (int i = 2; i*i < 1000001; ++i) {
		if (num[i] == false) {
			for (int j = i + i; j < 1000001; j += i) {
				num[j] = true;
			}
		}
	}

	int a, b;
	cin >> a >> b;
	for (int i = a; i <= b; ++i) {
		if (num[i] == false) {
			cout << i << '\n';
		}
	}
}