首页 > 代码库 > poj 3292 Semi-prime H-numbers
poj 3292 Semi-prime H-numbers
题目链接:http://poj.org/problem?id=3292
题目大意:就是给你一个模4余1的数H-number,如果一个H-number是H-primes 当且仅当它的因子只有1和它本身(除1外)。一个H-number是H-semi-prime当且仅当它只由两个H-primes的乘积表示。H-number剩下其他的数均为H-composite。给你一个数h,问1到h有多少个H-semi-prime数。
思路:这题坑惨啦,开始以为数据比较大,就在想办法优化打表,但是结果没想到直接暴力打表也行,坑死人啦。
我们用一个数组用来标记这个数,如果是H-semi-prime用1标记。最后统计。。。。。。。
code
#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<iostream> using namespace std; int countt=0; int prime[1000010]; int a[1000010]; void f() //打表函数 { int i,j; int sum=0; memset(prime,0,sizeof(prime)); for(i=5;i<=1000001;i=i+4) { for(j=5;j<=1000001;j+=4) { if(i*j>1000001) { break; } else { if(prime[i]==0&&prime[j]==0) //如果这两个数不是H-semi-prime就把他们的积标记唯一 { prime[i*j]=1; } else { prime[i*j]=-1; //标记为-1以防被当做H-primes用来计算。。。。 } } } } for(i=0;i<=1000001;i++) { if(prime[i]==1) { sum++; } a[i]=sum; } } int main() { int n; f(); while(scanf("%d",&n)==1&&n) { printf("%d %d\n",n,a[n]); } return 0; }
poj 3292 Semi-prime H-numbers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。