Submission #2457669

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int Max=4e4;
const int Len=1000000;
int prime[Max],prime1[Max];
int num[Len],flag[Len];
int n,m,number;
void is_prime()
{
    prime1[0]=1;
	prime1[1]=1;
	for(int i=2;i<Max;i++)
	{
		if(prime1[i]==0)
		{
		    prime[++number]=i;
			for(int j=i+i;j<Max;j+=i)
			{
				prime1[j]=1;
			}
		}
	}
}
int main()
{
    is_prime();
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(int i=1;i<=m-n+1;i++)
        {
            num[i]=n+i-1;
        }
        memset(flag,0,sizeof(flag));
        for(int i=1;i<=number;i++)
        {
            for(int j=1;j<=m-n+1;j++)
            {
                while(prime[i]<=num[j]&&num[j]%prime[i]==0)
                {
                    num[j]/=prime[i];
                    flag[j]++;
                }
            }
        }
        int sum=0;
        for(int i=1;i<=m-n+1;i++)
        {
            if(num[i]==1&&prime1[flag[i]]==0)
            {
                sum++;
            }
            else if(num[i]!=1&&prime1[flag[i]+1]==0)
            {
                sum++;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}

Submission Info

Judge Result