Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Problem A
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 < 10¹²).

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;
}