POJ 3292

http://acm.pku.edu.cn/JudgeOnline/problem?id=3292

题目意思:在1,5,9,13,17。。。4*n+1中,

H-primes:如5,9,13,因素只有1和其本身。

H-composites:在4*n+1中,除1和H-primes以外的数(n≥0)

H-semi-prime:恰好只由两个H-primes组成,可以存在多对符合要求的H-primes组合,例如:441=21*21=9*49;

输入一个H-numbers;

输出“H-numbers  H-numbers及之前的数是H-semi-prime的个数”

我开了一个 250,001 的数组来标记,开1000,0001的数组太费空间了,却而代之的是用4*i+1来表示某个数,而不是之间用i来表示

对于两个里的限制条件加以优化后,也可以减少很多不必要的时间;

然后就是标记时作判断,当prime[i] == 0时,就表示当前值是H-primes,== 1时,当前值是H-semi-prime,==3时。当前值是 非H-semi-prime的H-composites。只要prime[i] 和 prime[j] 都为H-primes(在两者中只要一个是H-semi-prime,那么就意味着

prime[temp] 是不符合要求的),

且prime[temp] 不是 非H-semi-prime的H-composites,那么prime[temp] 就是H-semi-prime。

刚做这题的时候没有头绪,一直在想筛选的方法,后来还是看了别人的代码,再经过自己的优化后内存速度都还可以。

途中经历了RE:筛选的时候数组越界了;

WA:输出漏了一个数。

1 for (i=1; i<250; i++)
2 {
3 for (j=i; ; j++)
4 {
5 temp = (((i<<2)+1)*((j<<2)+1)-1)>>2;
6 if (temp > 250000)
7 break;
8 if (prime[i]==0 && prime[j]==0 && prime[temp]!=3)
9 prime[temp] = 1; //是H-semi-prime
10   else
11 prime[temp] = 3; //不是H-semi-prime
12   }
13 }
原文地址:https://www.cnblogs.com/submarinex/p/1941236.html