poj3292 （H数）筛法

待我称王封你为后i 2024-02-17 21:33 51阅读 0赞

/*
    问题描述
    	形如4n+1的数被称为“H数”，乘法在“H数”组成的集合内是封闭的。在这个集合中只能被1和本身
    整除的数叫做“H-素数”（不包括1，H-素数并不是真正的素数，而是在H数集合中是素数），其余的数被称为“H-合数”。一个“H-合成数”是一个能且只能
    分解成两个“H-素数”乘积的“H-合数”（可能有多种分解方案）。比如441=21*21=9*49，所以441是
    “H-合成数”。125=5*5*5，所以125不是“H-合成数”。
    	求0~h范围内“H-合成数”的个数。
    	输入格式
    	输入若干行，每行一个小于等于1000001的整数h，一个0表示结束。
    	输出格式
    	对于每一行输入，输出一个数，表示答案。 
    Sample Input
    21 
    85
    789
    0
    Sample Output
    21 0
    85 5
    789 62
    */
    #include<cstdio>
    #include<iostream>
    using namespace std;
    int n;
    bool is_prime[1000100];//大约1M空间,是否为h素数 
    bool is_con[1000100];
    int main(){
    	//一次预处理 
    	for(int i=5;i<1000002/5;i+=4)
    	if(!is_prime[i])
    	for(int j=5;i*j<1000002;j+=4)
    		is_prime[i*j]=true;
    	for(int i=5;i*i<1000002;i+=4)
    	if(!is_prime[i])
    	for(int j=i;i*j<1000002;j+=4)
    	if(!is_prime[j])
    		is_con[i*j]=true;
    	while(scanf("%d",&n)&&n){
    		int ans=0;
    		for(int i=5;i<=n;i+=4)
    		if(is_con[i]) ans++;
    		printf("%d %d\n",n,ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，51人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj3292 （H数）筛法

/ 问题描述形如4n+1的数被称为“H数”，乘法在“H数”组成的集合内是封闭的。在这个集合中只能被1和本身整除的数叫做“H-素数”（不包括

待我称王封你为后i/ 2024年02月17日 21:33/ 0 赞/ 52 阅读

相关 POJ 2689【筛法求素数+区间筛素数】

Discription The branch of mathematics called number theory is about properties of numb

桃扇骨/ 2023年07月04日 06:15/ 0 赞/ 39 阅读

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 162 阅读

相关 Semi-prime-H-numbers(POJ-3292)题解

文章目录题目分析输入格式输出格式输入输出算法分析解题标称 ------------

╰+攻爆jí腚メ/ 2022年12月28日 11:16/ 0 赞/ 131 阅读

相关 POJ 3292-Semi-prime H-numbers（H半素数）

Semi-prime H-numbers <table> <tbody> <tr> <td><strong>Time Limit:</strong>&nbs

╰+哭是因爲堅強的太久メ/ 2022年07月10日 04:55/ 0 赞/ 156 阅读

相关素数基本（埃氏筛法/线性筛法）

一、检查n是否为素数最简单思路：所有可能的因数全部试一遍。 int gg(int n) { for(int i=2;i<n;i

拼搏现实的明天。/ 2022年05月17日 06:10/ 0 赞/ 284 阅读

相关素数筛法

//暴力枚举素数筛法 o(n 根号n) for(int i=2;i<=n;i++){ bool g=0; for(int j=2;jj<

╰+哭是因爲堅強的太久メ/ 2022年04月04日 10:54/ 0 赞/ 278 阅读

相关 Semi-prime H-numbers POJ - 3292 (数学打表)

This problem is based on an exercise of David Hilbert, who pedagogically suggested that

淡淡的烟草味﹌/ 2022年02月20日 13:48/ 0 赞/ 220 阅读

相关 POJ 3292, Semi-prime H-numbers

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 4166 Accepted: 1652 D

╰+哭是因爲堅強的太久メ/ 2021年12月22日 06:45/ 0 赞/ 171 阅读

相关筛法求欧拉函数（poj2478

求1～n的欧拉函数的值 include <iostream> include <cstdio> include <queue> include

谁践踏了优雅/ 2021年10月30日 01:38/ 0 赞/ 346 阅读