4394: 【基础】半质数(2007)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：14
解决：5
题目描述
上完体育课，小 T 同学去校园超市买了瓶水，喝完后就直接去机房上编程课了，给创 新实验班上编程课的 Q 教练曾经培养出过世界冠军金斌大神，这可是小 T 和他的小伙伴们 的偶象啊！小 T 同学从小学起就一直在金斌学长亲手开发的在线评测系统上提交程序，一 想起小学编程课眼前立刻浮现出 Q 教练的亲切笑容，想起自己初学编程时有些单词如 continue 等总是记不住，每当遇到这种情况 Q 教练总会不厌其烦地拼给自己听。
自从进入 初三后小 T 已经有很久没写程序了，也很久没见到和蔼可亲的 Q 教练了，今天这节课来得 太及时了，想到这里小 T 不由加快了脚步，走进机房，只见一阵凉风拍面而来，瞬间让人 神清气爽，原来 Q 教练知道我们上一节是体育课，早开好了空调在等我们了。
今天的编程 课 Q 教练一上来就抛给了大家一个高端大气的问题：编程寻找给定范围内的半质数。半质数小 T 还是第一次听说，这个问题明显比找质数档次高多了！ 质数的定义小 T 早在小学 就知道了，质数又称素数，指在大于 的自然数中，只能被 和本身整除的数， 也可定义为只有 和本身两个因数的数。
而半质数的定义是这样的：若对于一个正整数 ，恰好能够分解成两个质数的乘积，它就被称为半质数。比如，， 都是半质数， 不是半质数，它的质因子分解式为 ，分解出的质数共有 个，其中有 个质数 ， 个质数 。
输入
输入数据仅有一行包含两个用空格隔开的正整数 和 ，其中 。
输出
输出数据仅有一行包含一个整数表示在 到 之间共有多少个半质数。
样例输入 复制
4 26样例输出 复制
10提示
【样例解释】
在 到 之间共有 个半质数，分别是 , , , , , , , , , 。
【数据范围】
的数据满足：；
的数据满足：；
的数据满足：。
#include<bits/stdc++.h>
using namespace std;
/*
正整数N，恰好能分解成两个质数的乘积
问：s~e之间有多少个半质数
思路：
1.先筛除所有的素数
2.两两配对相乘，看能否构建出半质数（在s~e之间）
3.注意两个素数相乘，可能溢出int
*/
typedef long long LL;
const int N=5000010;
bool f[N];
int s,e,c=0;
int main(){
cin>>s>>e;
for(int i=2;i*i<=e;i++){
if(!f[i]){
for(int j=i+i;j<=e;j=j+i){
f[j]=true;
}
}
}
for(LL i=2;i*i<=e;i++){
if(!f[i]){
for(LL j=i;i*j<=e;j++){
if(i*j>=s&&!f[j]){
c++;
}
}
}
}
cout<<c;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
/*
正整数N，恰好能分解成两个质数的乘积
问：s~e之间有多少个半质数
思路：
1.先筛除所有的素数
2.两两配对相乘，看能否构建出半质数（在s~e之间）
3.注意两个素数相乘，可能溢出int
*/
typedef long long LL;
const int N=5000010;
bool f[N];
LL p[N],k;
int s,e,c=0;
int main(){
cin>>s>>e;
f[0]=true;
f[1]=true;
//筛素数
for(int i=2;i<=e;i++){
if(!f[i]){
p[++k]=i;
}
//筛素数
for(int j=1;i*p[j]<=e;j++){
f[i*p[j]]=true;
if(i%p[j]==0) break;
}
}
for(int i=1;i<=k;i++){
for(int j=i;j<=k;j++){
if(p[i]*p[j]>=s&&p[i]*p[j]<=e){
c++;
}
if(p[i]*p[j]>e) break;
}
}
cout<<c;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define MAXN 5000010
bool is_prime[MAXN];
int prime[MAXN];
//埃筛
int Er_Sieve(int n){
int tot=0;
memset(is_prime,1,sizeof(is_prime));
is_prime[1] = is_prime[0] = 0;
for(int i = 2;i <= n;i++){
if(!is_prime[i]) continue;
prime[++tot] = i; //prime[]存储了[1,n]的所有质数
for(int j = i*2; j <= n; j+=i)
is_prime[j]=0; //j为合数
}
return tot;
}
//线性筛（欧拉筛）
int Eu_Sieve(int n){
int tot=0;
memset(is_prime,1,sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int i = 2; i <= n; i++){
if(is_prime[i])
prime[++tot] = i; //prime[]存储了[1,n]的所有质数
for(int j = 1; j <= tot && prime[j]*i <= n; j++){ //关键一
is_prime[prime[j]*i] = 0;
if(i%prime[j] == 0) break;// 关键二
}
}
return tot;
}
int s,e,k,c=0;
int main(){
cin>>s>>e;
k=Er_Sieve(e);
for(int i=1;i<=k;i++){
for(int j=i;j<=k;j++){
if(prime[i]*prime[j]>=s&&prime[i]*prime[j]<=e){
c++;
}
if(prime[i]*prime[j]>e) break;
}
}
cout<<c;
return 0;
}