線形ふるい数-Homework(2015 Facebook Hacker Cup)

タイトル:Your first-grade math teacher,Mr.Book,has just introduced you to an amazing new concept-primes!According to your notes, a prime is a positive integer greater than 1 that is divisible by only 1 and itself. Primes seem fun, but without giving you and your 6-year-old colleagues time to consider their implications, he’s promptly gone on to define another term: primacity. He explains that the primacity of an integer is the number of distinct primes which divide it. For example, the primacity of 12 is 2 (as it’s divisible by primes 2 and 3), the primacity of 550 is 3 (as it’s divisible by primes 2, 5, and 11), and the primacity of 7 is 1 (as the only prime it’s divisible by is 7). Following his lesson, Mr. Book has given you homework with some rather mean questions of the following form: Given 3 integers A, B, and K, how many integers in the inclusive range [A, B] have a primacity of exactly K? Mr. Book probably expects his little homework assignment to take you and your classmates the rest of the year to complete, giving him time to slack off and nap during the remaining math classes. However, you want to learn more things from him instead! Can you use the skills you’ve learned in your first-grade computer science classes to finish Mr. Book’s homework before tomorrow’s math class?
入力:Input begins with an integer T,the number of homework questions.For each question, there is one line containing 3 space-separated integers:A, B, and K.
出力:For the ith question,print a line containing"Case#i:"followed by the number of integers in the inclusive range[A,B]with a primacity of K.
範囲:1≦T≦100 2≦A≦B≦107 1≦K≦109
Sample Input 5 5 15 2 2 10 1 24 42 3 1000000 1000000 1 1000000 1000000 2
Sample Output Case #1: 5 Case #2: 7 Case #3: 2 Case #4: 0 Case #5: 1
問題解:第一の方法は、最初に直接シミュレーションして、各数が何個の素数から構成されているかを求めて、結果は自然TLEです.
TLEコード:

#include 
#include 
#include 
#include 

using namespace std;

int dp[12345678];
int K;
bool isPrime (int num)
{
    if(dp[num] == 1)
    {
        return true;
    }
    if(dp[num] == -1)
    {
        return false;
    }
    for(int i=2;i*i<=num;i++)
    {
        if(num%i == 0)
        {
            dp[num] = -1;
            return false;
        }
    }
    dp[num] = 1;
    return true;
}

int primacity(int num)
{
    int cnt = 0;
    for(int i =2 ; i*i<=num;i++)
    {
        if(num%i==0)
        {
            if(isPrime(i) )
            {
                cnt++;
                //cout << i << endl;
            }

            if(isPrime(num/i)&& (num/i) !=i&&(num/i)<=num/2)
            {
                cnt++;
                //cout << num/i << endl;
            }
        }
    }
    if(isPrime(num))
    {
        cnt++;
        //cout << num << endl;
    }
    //cout << num << ":" << cnt << endl;
    return cnt;
}

int main()
{
    int T;
    int t=1;
    cin >> T;
    int A,B;
    while(t<=T)
    {
        scanf("%d%d%d", &A, &B, &K);
        int ans=0;
        for(int i=A; i<=B;i++)
        {
            if(primacity(i) == K)
            {
                //cout << i  << ":" << primacity(i) << endl;
                ans++;
            }

        }
        cout << "Case #" << t++ << ": " << ans << endl;
    }
}

第2の方法:線形ふるい素数は、算術の基本定理に基づいて、1より大きい整数ごとに、それ自体が質量数であるか、一連の質量数の積として書くことができるため、最小の質量数は2である.素数の倍数を直接求めることができます:1つのテーマの制定範囲の大きさの配列を創立して、2からその数の代表する下のマークがメモリに0を指すならば2から1回乗じて、得た数は下のマークとして、指すメモリ+1、この下付き文字を表す数には素数が含まれています(1回目の素数は2)次に最外層++,最外層数の下標が指すメモリが0であれば,その下標が素数であることを説明し,それを2から1回乗算し,0でなければその数が合数であることを説明し,スキップする.この線形ふるい素数の方法では,時間的複雑度が非常に低く,1回目の配列全体を計算した後の操作は直接クエリである.
ACコード:

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 10000010;
int KK[INF];
int K;
void primacity()
{

    for(int i=2;i<=INF; i++)
    {
        if( !KK[i])
        {
            KK[i]++;
            for(int j=2; i*j<=INF;j++)
            {
                KK[i*j]++;
            }
        }
    }
}

int main()
{
    primacity();
    int T;
    int t=1;
    cin >> T;
    int A,B;
    while(t<=T)
    {
        scanf("%d%d%d", &A, &B, &K);
        int ans=0;
        for(int i=A; i<=B;i++)
        {
            if(KK[i] == K)
            {
                //cout << i  << ":" << primacity(i) << endl;
                ans++;
            }

        }
        cout << "Case #" << t++ << ": " << ans << endl;
    }
}