Codeforces Global Round 4 Problem-D. Prime Graph

D. Prime Graph: http://codeforces.com/contest/1178/problem/D

题意：

有1-n, n个点，然后给这些点之间连上线，要求：

1. 无向图，没有重边和自环

2. n不必是素数

3. 边的总数是一个素数

4. 每个点的度必须是一个素数

输入一个n, 输出符合这些条件的边的个数和边。

分析：

有这样一个规律，设当前素数为x，下一个素数为y，则 y < x + x/2
所以先先把12345....n连成一个环，然后在这个环内连到边数为n的下一个素数，如果n就是素数，那么就不需要在环内连边了。

这样就有11条边，且每个点的度也都为素数。

注意：虽然与样例的答案不一样但也是对的，而且题目说的很清楚，不止一种情况，任意输出一种即可。

code：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10000;

int prime[MAXN];
void init()     // 初始化先筛选出素数
{
    prime[0] = prime[1] = 1;
    int n = sqrt(MAXN+1);
    for(int i=2; i<n; i++)
    {
        if(!prime[i])
        {
            for(int j=i+i; j<MAXN; j+=i)
                prime[j] = 1;
        }
    }
}
int graph[1000+7][1000+7];  // 存图

int main()
{
    init();
    int n;
    while(scanf("%d", &n) != EOF)
    {
        memset(graph, 0, sizeof(graph));
        int ans = 0;
        for(int i=1; i<n; i++)
        {
            graph[i][i+1] = 1;  // 存的时候只存一个就可以了，方便输出边。
            ans ++;   // 记录边的个数
        }
        graph[1][n] = 1; 
        ans ++;
        int i = 1, j = n-1; // 连环内的边，确保每个点的度不超过3
        while(j - i > 0)
        {
            if(!prime[ans]) // 边数为素数就可以终止了
                break;
            graph[i][j] = 1;
            ans ++;
            i++, j--;
        }
        // if(n%2 ==1 && !prime[ans])
        // {
        //     graph[(n+1)/2][n-1] = 1;
        //     ans ++;
        // }

        printf("%d\n", ans);
        for(int i=0; i<1007; i++)
        {
            for(int j=0; j<1007; j++)
            {
                if(graph[i][j])
                    printf("%d %d\n", i, j);
            }
        }
    }


    return 0;
}