3291. 素数个数排序

#include <stdio.h>
#include <math.h>
int isPrime(int n)
{
    int i, max=sqrt(n);
    if(n%2==0)
        return 0;
    for(i=3; i<=max; i+=2)
        if(n%i==0)
            return 0;
    return 1;
}
int main()
{
    int i, cnt=0;
    for(i=3; i<10001; i++) if(isPrime(i)) {printf("%d,",i); cnt++;}//输出质数加逗号（除2以外）
    printf("\n%d",cnt);//输出质数个数
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
typedef struct{int s, e, cnt;}Number;
int cmp(const void*a, const void*b)
{
    Number *p1=(Number*)a, *p2=(Number*)b;
    if(p1->cnt==p2->cnt)
    {
        if(p1->s==p2->s) return p1->e-p2->e;
        return p1->s-p2->s;
    }
    return p1->cnt-p2->cnt;
}
int main(void)
{
    int T, I;
    scanf("%d",&T);
    for(I=0; I<T; I++)
    {
        int n, i, j, k, prime[1229]={/*这里是质数表*/};
        Number num[10000];
        scanf("%d",&n);
        for(i=0; i<n; i++) scanf("%d %d",&num[i].s,&num[i].e);
        for(i=0; i<n; i++)
        {
            num[i].cnt=0;
            int start=num[i].s, end=num[i].e;
            for(k=0; k<1229; k++) if(prime[k]>=start) break;
            for(j=start; j<=end; j++)
                if(j==prime[k]) {k++; num[i].cnt++;}
        }
        qsort(num, n, sizeof(num[0]), cmp);
        printf("case #%d:\n",I);
        for(i=0; i<n; i++) printf("%d %d %d\n",num[i].s,num[i].e,num[i].cnt);
    }
    return 0;
}

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define MAXN 10000

//图 （第i个表示i是否为素数）
bool map[MAXN];
//快查表（第i个表示从0到i有多少素数）
int table[MAXN];
//读入数组 用来排序输出
int arr[MAXN][2];

inline int cmp(const void* a, const void *b) {
    int *left = (int*)a;
    int *right = (int*)b;

    int val1 = table[*(left+1)] - table[*left - 1] - (table[*(right+1)] - table[*right - 1]);
    if (val1 != 0)
        return val1;
    else {
        int val2 = *left - *right;
        if (val2 != 0)
            return val2;
        else
            return *(left+1) - *(right+1);
    }
}

int main() {

    //判定是否为素数 true不是素数 false是素数
    map[0] = map[1] = map[4]=true;
    for (int i = 6; i < MAXN; i++) {
        //快速判断，提高速度
        if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 ) {
            map[i] = true;
            continue;
        }
        //否则判断
        int middle = sqrt(i);
        for (int j = 3; j <= middle; j++) {
            if (i%j == 0) {
                map[i] = true;
                break;
            }
        }
    }

    //生成表（第i个表示从0到i有多少素数）
    for (int i = 1; i < MAXN; i++) {
        if (!map[i])
            table[i] = table[i - 1] + 1;
        else
            table[i] = table[i - 1];
    }

    //读入快排一下
    int times = 0;
    scanf("%d", &times);
    for (int s = 0; s < times; s++) {
        int num = 0;
        scanf("%d",&num);
        for (int i = 0; i < num; i++) {
            scanf("%d %d", &arr[i][0], &arr[i][1]);
        }

        qsort(arr, num, sizeof(int) * 2, cmp);

        printf("case #%d:\n", s);
        for (int i = 0; i < num; i++) {
            printf("%d %d\n", arr[i][0], arr[i][1]);
        }
    }

    return 0;
}

int val1 = table[*(left+1)] - table[*left - 1] - (table[*(right+1)] - table[*right - 1]);
if (val1 != 0)
    return val1;
else {
    int val2 = *left - *right;
    if (val2 != 0)
        return val2;
    else
        return *(left+1) - *(right+1);
}

//判定是否为素数 true不是素数 false是素数 
map[0] = map[1] = map[4]=true;
for (int i = 6; i < MAXN; i++) {
    //快速判断，提高速度
    if (i % 2 == 0 || i % 3 == 0 || i % 5 == 0 ) {
        map[i] = true;
        continue;
    }
    //否则麻烦的判断
    int middle = sqrt(i);
    for (int j = 3; j <= middle; j++) {
        if (i%j == 0) {
            map[i] = true;
            break;
        }
    }
}

//生成表（第i个表示从0到i有多少素数）
for (int i = 1; i < MAXN; i++) {
    if (!map[i])
        table[i] = table[i - 1] + 1;
    else
        table[i] = table[i - 1];
}

//读入快排一下
int times = 0;
scanf("%d", &times);
for (int s = 0; s < times; s++) {
    int num = 0;
    scanf("%d",&num);
    for (int i = 0; i < num; i++) {
        scanf("%d %d", &arr[i][0], &arr[i][1]);
    }

    qsort(arr, num, sizeof(int) * 2, cmp);

    printf("case #%d:\n", s);
    for (int i = 0; i < num; i++) {
        printf("%d %d\n", arr[i][0], arr[i][1]);
    }
}

return 0;

int main() {
    using namespace std;
    constexpr size_t PRIME_UBOUND = 10001;
    vector<bool> is_prime(PRIME_UBOUND, true);
    vector<uint32_t> prime_cnt(PRIME_UBOUND, 0);
    for (uint32_t i = 2; i < PRIME_UBOUND; ++i) {
        prime_cnt[i] = is_prime[i] + prime_cnt[i - 1];
        if (is_prime[i]) {
            for (uint32_t j = i << 1; j < PRIME_UBOUND; j += i) {
                is_prime[j] = false;
            }
        }
    }
    uint32_t t; cin >> t;
    for (uint32_t query = 0; query < t; ++query) {
        printf("case #%u:\n", query);
        uint32_t n; cin >> n;
        struct PrimeRange {
            uint32_t start, last, val;
            bool operator<(PrimeRange const& rhs) const {
                if (val == rhs.val) {
                    if (start == rhs.start) {
                        return last < rhs.last;
                    } else {
                        return start < rhs.start;
                    }
                } else {
                    return val < rhs.val;
                }
            }
        };
        vector<PrimeRange> ranges(n);
        for (auto& r : ranges) {
            cin >> r.start >> r.last;
            r.val = prime_cnt[r.last] - prime_cnt[r.start - 1];
        }
        sort(ranges.begin(), ranges.end());
        for (auto const& r : ranges) {
            printf("%u %u\n", r.start, r.last);
        }
    }
}