poj2649 Factovisors 质因数分解

质因数分解"/>

poj2649 Factovisors 质因数分解

需注意，判定的时候应该是分解出一个m的质因子就比较一次，而不是分解完后再比较，细节上处理要注意，比如当pr[i]不属于m的质因子时直接跳过，这样当m为一个大质数的时候不至于runtimr error

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100001
using namespace std;
bool valid[maxn];
int pr[100001],coun=0,n,m;
void Init()
{valid[1]=1;for(int i=2;i<maxn;i++){if(!valid[i])pr[coun++]=i;for(int j=2;i*j<maxn;j++)valid[i*j]=1;}
}
bool Check(int num,int counter)
{int coun=0;for(int i=num;i<=n;i++){int a=i;while(a%num==0){a/=num;coun++;}if(coun>=counter){return true;}}return false;
}
int main()
{Init();while(~scanf("%d%d",&n,&m)){bool ans=1;int s=m,now=0