ACM 10539 - Almost Prime Numbers

#include <stdio.h>
#include <stdlib.h>
#define MAXLEN 1000000

unsigned long long int ten12 = (long long int)1e12;
int prime[MAXLEN + 1] = {0};
unsigned long long int prime_tbl[80070] = {0};

void merge(unsigned long long int *data, unsigned long long int *left, unsigned long long int *right, int x, int y)
{
    int i, j, k;
    i = j = k = 0;

    while (i < x && j < y)
    {
        if (left[i] < right[j])
            data[k] = left[i++];
        else
            data[k] = right[j++];
        k++;
    }

    while (i < x)
        data[k++] = left[i++];

    while (j < y)
        data[k++] = right[j++];
}

void mergesort(unsigned long long int *data, int n)
{
    if (n <= 1) { return; }

    int x, y, i, j;
    unsigned long long int left[n/2], right[n - (n / 2)];
    x = n / 2;
    y = n - x;

    for (i = 0; i < x; i++)
        left[i] = data[i];

    for (i = 0; i < y; i++)
        right[i] = data[x + i];
    mergesort(left, x);
    mergesort(right, y);
    merge(data, left, right, x, y);
}

void makePrime()
{
    int i, j;
    for (i = 2; i <= MAXLEN; i ++)
        if(prime[i] > 0) continue;
        else
            for (j = 2; i * j <= MAXLEN; j ++)
                prime[i * j] ++;
    unsigned long long int p;
    int index = 0;
    for (i = 2; i <= MAXLEN; i ++)
        if (prime[i] == 0)
        {
            p = i;        
            while (p < ten12)
            {
                if (p != i) prime_tbl[index ++] = p;
                p *= i; 
            }
        }
    mergesort(prime_tbl, index);           
}

int main()
{
    makePrime();
    int i, n, count, lowIndex, highIndex;
    unsigned long long int low, high;
    scanf("%d", &n);
    while (n --)
    {
        count = 0;
        lowIndex = -1, highIndex = -1;
        scanf("%lld %lld", &low, &high);
        if (high <= MAXLEN)
        {
            for (i = low; i <= high; i ++)
                if (prime[i] == 1) count ++;
        }
        else 
        {
            for (i = 80069; i >= 0; i --)
            {
                if (prime_tbl[i] <= low && lowIndex == -1)
                {
                    if (prime_tbl[i] == low) count ++;             
                    lowIndex = i;
                    break;
                }
                if (prime_tbl[i] <= high && highIndex == -1)        
                    highIndex = i;
            } 
            count += highIndex - lowIndex;
        }
        printf("%d\n", count);        
    }
    return 0;
}

回目錄
回首頁