2012-07-13 09:11:03Morris
[UVA] 10539 - Almost Prime Numbers
Almost Prime Numbers
Time Limit: 1 second
Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.
Input
First line of the input file contains an integer N (N <= 600)
which indicates how many sets of inputs are there. Each of the next N
lines make a single set of input. Each set contains two integer numbers low and high (0 < low <= high < 1012).
Output
For each line of input except the first line you should produce one line
of output. This line contains a single integer, which indicates how
many almost prime numbers are within the range (inclusive) low…high.
| Sample Input | Sample Output |
3 1 10 1 20 1 5 |
3 4 1 |
Problemsetter: Shahriar Manzoor, special thanks to Derek Kisman
懶得二分了
#include <stdio.h>
#include <algorithm>
#define maxN 1000000000000LLU
#define maxL (1000000>>5)+1
using namespace std;
int p[80000], pt = 0;
int mark[maxL];
int GET(int x) { return mark[x>>5]>>(x&31)&1;}
void SET(int x) { mark[x>>5] |= 1<<(x&31);}
void sieve() {
int i, j, k;
int n = 1000000;
for(i = 2; i <= n; i++) {
if(!GET(i)) {
for(k = n/i, j = i*k; k >= i; k--, j -= i)
SET(j);
p[pt++] = i;
}
}
}
long long APN[160000];
int at = 0;
void build() {
int i;
for(i = 0; i < pt; i++) {
long long tmp = (long long)p[i]*p[i];
while(tmp <= maxN) {
APN[at++] = tmp;
tmp = tmp*p[i];
}
}
}
int main() {
sieve();
build();
int t;
long long a, b;
sort(APN, APN+at);
scanf("%d", &t);
while(t--) {
scanf("%lld %lld", &a, &b);
int cnt = 0, i;
for(i = 0; i < at; i++)
if(a <= APN[i] && APN[i] <= b)
cnt++;
printf("%d\n", cnt);
}
return 0;
}