//两个数如果不是互质，那么它们一定有一个质数因子
//用vec存入2到n的所有的质数因子
//用vis存入有该因子的数是否读入
//处理时只需要维护vis这个数组就行
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std ;
const int maxn = 100010 ;
vector<int> vec[maxn];
int isp[maxn] ;
int vis[maxn] ;
int num[maxn] ;
void set()
{
memset(isp, 0 ,sizeof(isp)) ;
isp[1] = 1;
for(int i = 2;i < maxn ;i += 2)
{
isp[i] = 1;
vec[i].push_back(2) ;
}
for(int i = 3;i < maxn ;i++)
{
if(isp[i])continue ;
for(int j = i;j < maxn ;j+=i)
{
isp[j] = 1;
vec[j].push_back(i) ;
}
}
}
int main()
{
//freopen("input.txt" ,"r",stdin) ;
set() ;
int n , m ;
char ch;int i ;
while(~scanf("%d%d" ,&n , &m))
{
memset(num , 0 , sizeof(num)) ;
memset(vis , 0 , sizeof(vis)) ;
while(m--)
{
scanf("%c%c%d" ,&ch ,&ch, &i) ;
//cout<<ch<<endl;
if(ch == ‘-‘)
{
//cout<<i<<endl;
if(!num[i])puts("Already off");
else
{
puts("Success");
num[i] = 0;
for(int j = 0;j < vec[i].size() ;j++)
vis[vec[i][j]] = 0;
}
}
if(ch == ‘+‘)
{
if(num[i])puts("Already on");
else
{
int flag = 0 ;
for(int j = 0;j < vec[i].size();j++)
{
int t = vec[i][j] ;
if(vis[t])
{
printf("Conflict with %d\n" , vis[t]) ;
flag = 1;
break;
}
}
if(!flag)
{
puts("Success");
// cout<<i<<endl;
num[i] = 1;
for(int j = 0;j < vec[i].size();j++)
vis[vec[i][j]] = i;
}
}
}
}
}
return 0 ;
}
Codeforces Round #109 (Div. 1)B 数论
原文：http://blog.csdn.net/cq_pf/article/details/45370697
