소수 구하기 #1929 c++ 풀이

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

1929번: 소수 구하기

생각 :

1. 소수 구해서 그냥 검사하면 되겠구나 ! => 시간초과

2. bineary search의 조건을 잘 주면 되나? => 해결하지 못함

3. 모든 소수를 구하되, 배수를 지워볼까? => 정답

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;


vector <int> numbers;
long long int primes[1000001];


bool getAllPrime(int M, int N) {
	for (int i = M; i <= N; i++) {
		primes[i] = i;
		
	}
	
	for (int i = 2; i <= N; i++) {
		if (primes[i] == -1)continue;
		int j = i; 
		while (j <= N) {
			if (j *i > N)break;
			primes[i * j] = -1;
			j = j +1;
		}
		
		
	}
	//for (int i = 0; i <= N; i++) {
	//	cout << primes[i] <<'\n';
	//
	//}
	primes[1] = -1;
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int M, N;
	cin >> M >> N;
	for (int i = M; i <= N; i++) {
		primes[i] = -1;
	}
    
	getAllPrime(M, N);
	for (int i = M; i <= N; i++) {
		if (primes[i] != -1)cout << primes[i] << '\n';
   }
	return 0;
}

 

반복문의 조건을 i*i<=N으로 해도 괜찮다는데 그 이유를 잘 모르겠다.

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<map>
#include<algorithm>
using namespace std;


vector <int> numbers;
int primes[1000001];


bool getAllPrime(int M, int N) {
	for (int i = M; i <= N; i++) {
		primes[i] = i;
		
	}
	
	for (int i = 2; i*i <= N; i++) {
		if (primes[i] == -1)continue;
		int j = i; 
		while (j <= N) {
			if (j *i > N)break;
			primes[i * j] = -1;
			j = j +1;
		}
		
		
	}

	primes[1] = -1;
	return true;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int M, N;
	cin >> M >> N;
	for (int i = M; i <= N; i++) {
		primes[i] = -1;
	}
    
	getAllPrime(M, N);
	for (int i = M; i <= N; i++) {
		if (primes[i] != -1)cout << primes[i] << '\n';
   }
	return 0;
}

이 방식은, 찾아보니 에라토스테네스의 체라는 알고리즘이었다..