德州 网站建设,被网站管理员设置拦截,创建全国文明城市要求街巷,出租网站空间显然#xff0c;死做枚举只能的50分。
错了4次总算对了。
大体思路#xff1a;
因题目说只有两个因数#xff0c;那么有两种情况#xff1a; 1#xff1a;两个质数相乘#xff0c;如#xff1a;3*515 5*745 等#xff08;不包括5*525 或5*315 重复计算\ 因为3*5算了… 显然死做枚举只能的50分。
错了4次总算对了。
大体思路
因题目说只有两个因数那么有两种情况 1两个质数相乘如3*515 5*745 等不包括5*525 或5*315 重复计算\ 因为3*5算了/ 2特别容易忽略 注为质数
我是这样编的
1.剪枝筛选算出质数
2.for(i1;in;i) if(是质数) 保存。
3.枚举质数个数判断能和几个数进行质数相乘且n二分答案个数-i
4.判断 注为质数答案
5.cout
易错点保存质数的数组要
#include bits/stdc.h #pragma GCC optimize(Ofast) using namespace std; int n,i,f[10000100],j;long long b[5000010]; int sum,t,w,mid,bao,ans; main(){ ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cinn;f[1]1; for(i4;in;i2)f[i]1; for(i3;isqrt(n);i) if(f[i]0)for(ji*2;jn;ji)f[j]1;//剪枝筛选 for(i2;in;i) if(f[i]0)b[sum]i;//个数 for(i1;isum;i){ ti1;wsum;bao0; while(tw){ mid(tw)/2; if(b[mid]*b[i]n) tmid1,baomid; else wmid-1; }//二分 if(bao0)break;//优化 else{ ansbao-i;//答案格式-i-i是去重 } } for(i2;i*i*in;i)//3次方的加加 if(f[i]0)ans; coutans; }
#include bits/stdc.h
#pragma GCC optimize(Ofast)
using namespace std;
int n,i,f[10000100],j;long long b[5000010];
int sum,t,w,mid,bao,ans;
main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cinn;f[1]1;for(i4;in;i2)f[i]1;for(i3;isqrt(n);i)if(f[i]0)for(ji*2;jn;ji)f[j]1;//剪枝筛选for(i2;in;i)if(f[i]0)b[sum]i;//个数for(i1;isum;i){ti1;wsum;bao0;while(tw){mid(tw)/2;if(b[mid]*b[i]n) tmid1,baomid;else wmid-1;}//二分if(bao0)break;//优化else{ansbao-i;//答案格式-i-i是去重}}for(i2;i*i*in;i)//3次方的加加if(f[i]0)ans;coutans;
}
