에라토스테네스의 체

1) 소수간 비교

#include <bits/stdc++.h>
using namespace std;
const int N=1000000;
int cnt=0;
vector<int> p;
int main(){
	p.push_back(2);
	for(int i=3; i<=N; i+=2){
		bool ch=1;
		for(int j=1; j<p.size() && p[j]*p[j]<=i; ++cnt,++j) if(i%p[j]==0) {ch=0; break;}
		if(ch) p.push_back(i), printf("%d %d\n",i,cnt);
	}
	printf("%d",p.size());
}

2) 배열체크

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1000000;
ll cnt=0;
bool v[N+2];
vector<int> p;
int main(){
	p.push_back(2);
	for(ll i=3; i<=N; i+=2){
		if(v[i]) continue;
		printf("%lld %lld\n",i,cnt);
		v[i]=1; p.push_back(i);
		for(ll j=i*i; j<=N; j+=i*2) v[j]=1, cnt++;
		
	}
	printf("%d",p.size());
}

 

아무생각없이 1번으로 짜고 다녔는데

2번이 훨씬 훨씬 더 빠르다.

와!