POJ 3292 - Semi-prime H-numbers


问题描述

一个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数。

解题思路

感觉跟同余模扯不上关系。

筛法打表,再直接输出。

水题。

AC 源码

//Memory Time 
//4172K  63MS 

#include<iostream>
using namespace std;

const int size=1000001;

int H_Number[size+1];

/*筛法打表*/
void Table(void)
{
    memset(H_Number,0,sizeof(H_Number));  //H_Number[i]=0 表示 i为H-prime

    for(int i=5;i<=size;i+=4)
    {
        for(int j=5;j<=size;j+=4)
        {
            int multiply=i*j;
            if(multiply>size)
                break;

            if(H_Number[i]==0 && H_Number[j]==0)  //i与j均为H-prime
                H_Number[multiply]=1;  //multiply为H-semi-primes
            else
                H_Number[multiply]=-1; //multiply为H-composite
        }
    }

    int Pcount=0; //H-prime计数器
    for(int k=1;k<=size;k++)
    {
        if(H_Number[k]==1)
            Pcount++;
        H_Number[k]=Pcount;   //从1到k有Pcount个H-semi-primes
    }
    return;
}

int main(void)
{
    Table();
    int h;
    while(cin>>h && h)
        cout<<h<<' '<<H_Number[h]<<endl;

    return 0;
}

相关资料


文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1936 - All in All POJ 1936 - All in All
POJ 1936 - All in All Time: 1000MS Memory: 30000K 难度: 初级 分类: 串 问题描述无。 解题思路水题一道,直接去模拟吧。 在s2中找s1的子串而已,本来还想用LCS的,后来想想,这样空
2011-05-01
下一篇 
POJ 3126 - Prime Path POJ 3126 - Prime Path
POJ 3126 - Prime Path Time: 1000MS Memory: 65536K 难度: 初级 分类: BFS 问题描述给定两个四位素数a b,要求把a变换到b 变换的过程要保证 每次变换出来的数都是一个 四位素数
2011-04-26
  目录