题目链接:uva 11105 - Semi-prime
H-numbers
题目大意:H-number为4∗k+1(k为非负数),H-composites为因子中含有H-number(不包括自己本身)的数,反之久是H-prime,给定n,求有多少H-composites。
解题思路:首先用筛选法求出范围内的H-prime,然后枚举两个判断乘积是否在范围内。
#include <cstdio>
#include <cstring>
const int maxn = 1e6+5;
typedef long long ll;
int v[maxn], prime[maxn], cp;
void primeHtable(int n) {
cp = 0;
memset(v, 0, sizeof(v));
for (int i = 5; i < n; i += 4) {
if (v[i])
continue;
prime[cp++] = i;
for (int j = i * 2; j < n; j += i)
v[j] = 1;
}
}
int solve (int n) {
int ans = 0;
memset(v, 0, sizeof(v));
for (int i = 0; prime[i] < n && i < cp; i++) {
if ((ll)prime[i] * prime[i] > n)
break;
for (int j = i; prime[j] < n && j < cp; j++) {
ll u = (ll)prime[i] * prime[j];
if (u > n)
break;
if (v[u])
continue;
ans++;
v[u] = 1;
}
}
return ans;
}
int main () {
primeHtable(maxn);
int n;
while (scanf("%d", &n) == 1 && n) {
printf("%d %d\n", n, solve(n));
}
return 0;
}
分享到:
相关推荐
数论 Prime Numbers, Friends Who Give Problems- A Trialogue with Papa Paulo.pdf
算法-数论- 斐波那契数列(Fibonacci).rar
算法-数论- 约数.rar
算法-数论- 逆元.rar
算法-数论- 概述.rar
算法-数论- 整式方程.rar
算法-数论- 整数分解.rar
算法-数论- 莫比乌斯反演.rar
算法-数论- 快速幂.rar
算法-数论- 欧拉函数.rar
算法-数论- 素性测试.rar
算法-数论- 毕达哥拉斯三元组.rar
算法-数论- 线性同余方程.rar
算法-数论- 整除与同余.rar
算法-数论- 佩尔方程与连分数.rar
算法-数论- 逆元与同余式定理.rar
算法-数论- 最大公约数与最小公倍数.rar
初等数论及其应用-第五版-华章-Kenneth.H.Rosen
好的资源,学好数论。教材整理-新课标其它.zip,请好好好好好好好哦啊
算法-数论- 高次同余方程与 BSGS 算法.rar