URI (BEECROWD) - 3165 - Twin Prime (Primos Gêmeos) - Matemática - C, C++ e Haskell

Fala, pessoal! Novidade por aqui! Um problema de matemática resolvido.

Eu sei que não costumo resolver muitos problemas dessa categoria, mas vou tentar trazer mais para vocês. E para compensar isso, resolvo o problema Primos Gêmeos (Twin Prime) em três linguagens.

Bora conferir?

Plataforma: URI (BEECROWD)

Problema: 3165

Linguagens: C, C++ e Haskell

Enunciado:

Escreva um programa que dado um inteiro N, imprima os números primos gêmeos mais próximos menores ou iguais a N.

De acordo com a wikipedia, "Um primo gêmeo é um número primo que é 2 a menos ou 2 a mais que outro número primo - por exemplo, qualquer membro do par primo gêmeo (41, 43). Em outras palavras, um primo gêmeo é primo que tem um intervalo de dois ".

Solução:

A estratégia geral adotada envolve salvar o maior entre os pares de primos gêmeos e identificar quando o número informado é maior que algum desses números, imprimindo ele e ele-2.

Código em C:

Minha solução envolve já preparar um array contendo os valores de primos gêmeos maiores. Ou seja, se 41 e 43 são primos separados por 2 unidades, salvo apenas o 43. Primeiramente, defino a resposta como 883, pois é o maior primo gêmeo possível. Se o valor do primo gêmeo da posição analisada do array ultrapassar o valor de n, significa que a resposta é o valor lido anteriormente (o valor do array na posição atual menos um). Como eu preciso dos dois primos gêmeos, imprimo primeiro o valor-2 e depois o próprio valor (que está na variável resposta).

#include <stdio.h>
#define TAM 34
int main() {

   long long int primosGemeos[TAM] = {5, 7, 13, 19, 31, 43, 61, 73, 103, 109, 139, 151, 181, 193, 199, 229, 241, 271, 283, 313, 349, 421, 433, 463, 523, 571, 619, 643, 661, 811, 823, 829, 859, 883};
   long long int n;
   long long int i;
   long long int resposta = 883;
   
   scanf("%lld", &n);

   for (i = 0; i < TAM; i++) {
      if (n < primosGemeos[i]) {
         resposta = primosGemeos[--i];
         break;
      }
   }
   printf("%lld %lld\n", resposta - 2, resposta);
   return 0;
}

Código em C++:

Esse código usa a mesma estratégia do código C.

#include <iostream>

using namespace std;

int main() {
   const int TAM = 34;
   long long int primosGemeos[TAM] = {5, 7, 13, 19, 31, 43, 61, 73, 103, 109, 139, 151, 181, 193, 199, 229, 241, 271, 283, 313, 349, 421, 433, 463, 523, 571, 619, 643, 661, 811, 823, 829, 859, 883};
   long long int n;
   long long int resposta = 883;
   cin >> n;
   for (int i = 0; i < TAM; i++) {
      if (n < primosGemeos[i]) {
         resposta = primosGemeos[--i];
         break;
      }
   }
   cout << resposta - 2 << " " << resposta << endl;
   return 0;
}

Código em Haskell:

Em Haskell eu acabei fazendo uma função primosAte1000, que retorna a lista de maiores primos gêmeos, e uma função para obter a resposta, que percorre essa lista até encontrar o maior primo gêmeo menor que n.

obtemResposta :: Int -> Int -> [Int] -> Int
obtemResposta n c [] = 883
obtemResposta n c (x:xs)
   | x > n = primosAte1000!!(c-1)
   | otherwise = obtemResposta n (c+1) xs

primosAte1000 :: [Int]
primosAte1000 = [5, 7, 13, 19, 31, 43, 61, 73, 103, 109, 139, 151, 181, 193, 199, 229, 241, 271, 283, 313, 349, 421, 433, 463, 523, 571, 619, 643, 661, 811, 823, 829, 859, 883]
main :: IO ()

main = do

   n <- readLn

   let resposta = obtemResposta n 0 primosAte1000

   putStrLn (show (resposta - 2) ++ " " ++ show resposta)

Espero que tenham gostado! Chave PIX (chave aleatória) para doações: 6d8bc7a8-5d74-493a-ab7a-3515baf35956. Qualquer valor ajudará muito, obrigado mais uma vez!