[C++] Prime number

0. 합성수 N에서 1을 제외한 가장 작은 약수는 root(N)이하이다. 

1. 1부터 n까지 모든 소수 찾기 

#include <bits/stdc++.h>
using namespace std;
vector<int> isprime(int n) {
	vector<int> primes; 
    for (int i =2; i <= n; i++) {
    	bool isprime = 1; 
        for (auto p : primes) {
        	if (p * p > i) break; 
            if (i % p == 0) {
            	isprime = 0; 
                break;
            }
        }
        if (isprime) primes.push_back(i); 
    }
}

4 이상의 모든 합성수는 약수의 최솟값이 prime number다. 따라서, primes에 소수를 추가해 주면서, 소수판별을 진행한다.

 

2. 에라토테네스의 체 

#include <bits/stdc++.h>
using namespace std;

vector<int> eratos(int n) {
	vector<int> primes; 
	vector<bool> numbers(n + 1, true); 
	numbers[1] = false;
	for (int i = 2; i <= n; i++) {
		if (!numbers[i]) continue;
		for (int j = 2 * i; j <= n; j += i) {
			numbers[j] = false; 
		}
	}
	for (int i = 1; i <= n; i++) {
		if (numbers[i]) primes.push_back(i);
	}
	return primes;
}

 에라토스테네스의 체로 소수를 쉽게 판별할 수 있다. 

여기서 더 최적화를 할 수 있다고 한다. 

#include <bits/stdc++.h>
using namespace std;

vector<int> eratos(int n) {
	vector<int> primes; 
	vector<bool> numbers(n + 1, true); 
	numbers[1] = false;
	for (int i = 2; i * i <= n; i++) {
		if (!numbers[i]) continue;
		for (int j = i * i; j <= n; j += i) {
			numbers[j] = false; 
		}
	}
	for (int i = 2; i <= n; i++) {
		if (numbers[i]) primes.push_back(i);
	}
	return primes;
}

첫 번째 for문을 i * i <= n 까지만 실행되게 한다. 예를 들어, n = 100일 때, 10까지만 loop를 돌리면 된다.  또한, 두 번째 loop도 i * i부터 시작을 한다. (아직 이해가 가진 않지만, 언젠가는 이해가 가겠지요)

참고한 자료: https://www.youtube.com/watch?v=2RCJApSVxRI&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=19

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전