一、线性筛


const int maxn=1000006;
int prime[maxn];
bool ha[maxn];
int mu[maxn];
int cnt=0;
void Mu(void)
{
    mu[1]=1;
    ha[1]=true;
    for(int i=2;i<maxn;i++)
    {
        if(!ha[i])
        {
            mu[i]=-1;
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&(ll)i*prime[j]<maxn;j++)
        {
            ha[i*prime[j]]=true;
            if(i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    return ;
}

二、
这是个啥我也给忘掉了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int p[50010],n;

int prime(int m)
{
	int temp=0,k=m;
	for(int i=2;i*i<=k;i++)
		if(!(m%i))
		{
			temp++; m/=i;
			if(!(m%i)) return 0;
		}
	if(m>1) temp++;
	return (temp&1)?-1:1;
}

int main()
{
	for(int i=1;i<=50000;i++)
		p[i]=p[i-1]+prime(i);

	cin>>n;

	FILE *fp;
	//fp=fopen("zap.out","w");
	for(int i=1;i<=n;i++)
	{
		int a,b,c,d;
		scanf("%d%d%d",&a,&b,&d);
		a/=d; b/=d;

		if(a>b) swap(a,b);
		int ans=0;

		for(int j=1;j<=a;j=c+1)
		{
			c=min(a/(a/j),b/(b/j));
			ans+=(p[c]-p[j-1])*(a/j)*(b/j);
		}
		printf("%d\n",ans);
	}
	//fclose(fp);
	return 0;
}