线性筛素数

线性筛（欧拉筛）

原理：每个数都被其最小的质因数筛掉

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

vector<int> prime;
bool mmap[100000001];

bool isPrime(int a)
{
	for(int i=2;i<=a;i++)
	{
		if(mmap[i]==false) 
		{
			prime.push_back(i);
		}
		for(int j : prime)
		{
			if(j*i>a) break;
			mmap[i*j]=true;
			if(i%j==0) break;
		}
	}
	return mmap[a];
}

int main()
{
	int n;
	cin>>n;
	cout<<!isPrime(n);
	return 0;
}