思路

这道题目是筛选求质数的衍生，可以直接用模拟+枚举完成。这道题目可以写prime求解。

这道题目主要的难点就在预处理上。这道题目需要限定范围，使用两个数组(同时开两个数组以方便求值，用pair<int,int>也可以)。这道题要用双循环，第一层从2循环到E，第二层选定乘数范围（不大于E,否则死循环超时),同时避免重复(i*b[j]<m),最后求i/a[i]是否等于a[i/a[i]]。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5000005;
int a[maxn], b[maxn], s, e, t, ans = 0;
int main()
{
	cin >> s >> e;
	for (int i = 2; i <= e; i++)//1不是素数 
	{
		if (!a[i])
            b[t++] = a[i] = i;
		for (int j = 0; j < t && i * b[j] <= e; j++)
		{
			a[i * b[j]] = b[j];
			if (a[i] == b[j])
                break;
		}
	}
	for (int i = s; i <= e; i++)
        ans += (a[i / a[i]] == i / a[i]);
	cout << ans;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e6+10;
bool f[N];
int primes[N],l,r,k,ans; 
int main(){
	scanf("%d%d",&l,&r);
	for (int i=2;i<=r;i++){
		if (!f[i])primes[++k]=i;
		for (int j=1;primes[j]*i<=r;j++){
			f[primes[j]*i]=true;
			if (i%primes[j]==0)break;
		}
	}
	for (ll i=2;i*i<=r;i++){
		if (!f[i]){
			for (ll j=i;j*i<=r;j++){
				if (!f[j]&&j*i>=l)ans++;
			}
		} 
		
	}
	printf("%d",ans);
	return 0;
}

60分做法：暴力找

#include <cstdio>
//筛素数+暴力枚举
inline int reader(){
	int it = 0 , chr = getchar() ;
	while('0' > chr || chr > '9')
		chr = getchar() ;
	while('0' <= chr && chr <= '9')
		it = (it << 1) + (it << 3) + chr - '0' , chr = getchar();
	return it ;
}

bool u_prime[5000005] ;
int st , ed , primes[500000] , pi , ans; 

int main(){
	st = reader() ;
	ed = reader() ;
	u_prime[0] = u_prime[1] = true ;
	for(int i = 2 ; i <= ed ; i ++)
		if(!u_prime[i]){
			primes[pi++] = i ;
			for(int j = i * 2 ; j <= ed ; j += i)
				u_prime[j] = true ;
		}
	for(int i = st ; i <= ed ; i ++){
		for(int j = 0 ; j < pi ; j ++){
			if(i % primes[j] == 0 && !u_prime[i / primes[j]]){
				ans ++ ;
				break ;
			}
		}
	}
	printf("%d" , ans) ;
	return 0 ; 
}

100分做法

#include <cstdio>

inline int reader(){//快读，对这道题影响不大，cin也行
	int it = 0 , chr = getchar() ;
	while('0' > chr || chr > '9')
		chr = getchar() ;
	while('0' <= chr && chr <= '9')
		it = (it << 1) + (it << 3) + chr - '0' , chr = getchar();
	return it ;
}

bool u_prime[5000005] , NBprime[5000005] , vis[5000005];
int st , ed , pi , ans , primes[348514]; 
//5000000内一共348513质数，所以定义primes[348514]够了
//筛了一遍算出来的

int main(){
	st = reader() ;
	ed = reader() ;
	u_prime[0] = u_prime[1] = true ;
	for(int i = 2 ; i <= ed ; i ++)
    //修改过的筛素数
		if(!u_prime[i]){
			primes[pi ++] = i ;
			for(int j = i * 2 ; j <= ed ; j += i)
				u_prime[j] = true ;
            //所谓半质数，就是质数*质数
            //现在确保i是质数，再乘质数j得到的就是一个半质数
			for(int j = 0 ; primes[j] * i <= ed && j < pi; j ++)
				NBprime[i * primes[j]] = true ;
		}
	for(int i = st ; i <= ed ; i ++)
		ans += NBprime[i] ;
	printf("%d" , ans) ;
	return 0 ; 
}