[C++] 純文本查看 復制代碼
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
#define MAX 1000001
bool isnp[MAX]={true,true,false};
int dp[MAX]={0};
vector<int> prime;
int main()
{
int A=2,B,ans;
while(A<1001)
{
if(!isnp[A])
{
B=A*A;
while(B<MAX)
{
isnp[B]=true;
B+=A;
}
}
++A;
}
for(int i=1;i<MAX;++i)
{
dp = dp[i-1];;
if(!isnp)
{
dp++;
prime.push_back(i);
}
}
/*
A! = 1*2*3*..*A
B! = 1*2*3*..*A*...B
A!+B! = A!(1+(A+1)*(A+2)*...B)
(1+(A+1)*(A+2)*...B) is prime?
*/
while(cin>>A>>B)
{
if(A>B)swap(A,B);
ans=dp[A];
ll left = 1;
for(ll i=A+1;i<=B;++i)
left=left*i;
++left;
for(int i=0; i<prime.size() && prime<=A ;++i)
{
while( left % prime ==0 )left/=prime;
}
for(int c:prime)
{
if( left%c ==0 )
{
ans++;
while( left%c ==0 )left/=c;
}
}
if(left>1)ans++;
cout<<ans<<'\n';
}
}
