Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

UVA 10394

Autor: Caique Garutti

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

long long primosGemeos[100001];
long long primosTeste[20000010];
long long primos[20000010];
long long qtosPrimosGemeos = 0;
long long qtosPrimos = 0;

int populaPrimos() {
        double limitDouble = sqrt(20000000.0) + 1;
        long long limit = limitDouble;
        for (long long i = 2; i < limit;i++) {
                if (primosTeste[i] != -1) {
                        primos[qtosPrimos++] = i;
                        for (long long j = i*i; j < 20000000; j+= i) {
                                primosTeste[j] = -1;
                        }
                }
        }
        for (long long i = limit; i < 20000000; i++) {
                if (primosTeste[i] != -1) {
                        primos[qtosPrimos++] = i;
                }
        }
        return 1;
}

int populaPrimosGemeos() {
        for (long long i = 1; i < qtosPrimos; i++) {
                if (primos[i-1] +2 == primos[i]) {
                        primosGemeos[qtosPrimosGemeos++] = primos[i-1];
                        if (qtosPrimosGemeos >= 100002) {
                                break;
                        }
                }
        }

        return 1;
}

int main() {
        long long numero;
        populaPrimos();
        populaPrimosGemeos();
        while(scanf("%lld",&numero) != EOF) {
                printf("(%lld, %lld)\n",primosGemeos[numero-1],primosGemeos[numero-1] + 2);
        }

        return 0;
}