Skip to content

Instantly share code, notes, and snippets.

@tnaia
Last active August 29, 2015 14:25
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save tnaia/28d0e8985170ccf024fa to your computer and use it in GitHub Desktop.
Uma brincadeira com a sintaxe de programação letrada e markdown

1001 primos

Este texto é um programa letrado (PL) usando C e markdown.

Ele é também um teste de sintaxe (e não uma prova de conceito de PL).

Vamos imprimir os 1001 menores números primos.

Nota. A programação letrada é um conceito de Knuth. Knuth e Levy Escreveram um sistema para programação letrada usando $TeX$ e C.

Uma rede C com markdown

Que tal usar markdown como marcação para uma rede em C? Uma vantagem é que há pouca interação entre os operadores dessas linguagens. Abrimos mão do controle tipográfico fino do $\TeX$, mas não de fórmulas (pense MathJax).

Dando nomes aos bois

Os bocados (chunks) que formam a rede podem (ou não) ter nomes. Um bocado tem três partes: uma parte texto, uma parte para definições de macros, e uma parte código. Cada uma dessas partes é opcional. Pense no texto como um espaço informal para elaborar a notação (formal) do programa. (Se isso soou acadêmico, bingo! O pessoal da matemática têm uma boa experiência com o delicado balanço entre as linguagens formal e natural.)

Se alterar o programa, atualize o banner.

#define banner "Olá, sou PRIMOS, (versão 0.9)\n"

Corpo do programa

O programa é bastante simples

#include <stdio.h> /* para `printf` */

#define quantos_primos 1001

int
main (int argc, char **argv)
{
  <Variáveis de `main`>
  
  printf (banner);
  <Imprime primos>
  
  printf ("Até mais!\n");
  return 0;
}

Imprimindo primos

Testamos se o número n é primo, imprimindo se for o caso.

O array primos[0..encontrados -1] contém os números primos menores do que n.

Como o único número primo par é 2, só precisamos testar a primalidade dos números ímpares $3,5,7,9,\ldots$.

<Imprime primos>=
primos[0] = 2;
encontrados = 1; /* encontramos 1 primo até agora */
n = 3; /* candidato a primo */

printf ("Primos: 2");
while (<Faltam primos>)
  {
    <Incremente `n` até o próximo primo>

    printf (", %d", n);

    primos[encontrados++] = n;
    n += 2; /* testamos só os números ímpares */
  }
<Faltam primos>=
encontrados < quantos_primos

<Variáveis de `main`>=
int primos[quantos_primos];
int i, n, encontrados;

Qual é o próximo primo?

n é primo se e somente se ele não possui divisores em primos[0..encontrados -1].

Uma otimização: podemos decidir que n é primo se não é divisível por algum primo menor ou igual a $\sqrt{n}$. Por sorte, primos[0,...encontrados -1] está sempre ordenado.

Porque podemos parar em $\sqrt{n}$? Se $n$ não é primo, existem números $a$ e $b$ tais que $n = ab$, e um entre esses números é menor ou igual a $\sqrt{n}$. Isso porque se $a$ e $b$ fossem ambos maiores do que $\sqrt{n}$, teríamos $ab &gt; \sqrt{n}\sqrt{n} = n$ ou seja, $ab$ é maior do que $n$, um absurdo. Segundo a Wikipedia:

[. . .] The property of being prime (or not) is called primality. A simple but slow method of verifying the primality of a given number $n$ is known as trial division. It consists of testing whether $n$ is a multiple of any integer between 2 and $\sqrt{n}$.

<Incremente...>=
i = 0;
while (<`primos[i]` é um primo menor ou igual a $\sqrt {n}$>)
  if (n % primos [i] == 0)
    {
      n += 2; /* testamos só os números ímpares */
      i = 0;
    }
  else
    ++i;  
<`primos[i]` é um primo menor ou igual a $\sqrt{n}$>=
i < encontrados && primos [i] * primos [i] <= n

Comentários finais

Nem todo bocado tem título, mas eles devem ser numerados, para que seja possível navegar entre eles com links. Por isso tem apenas um jogo-da-velha seguido por dois espaços # (dá pra ver melhor na versão raw deste arquivo).

Aqui nós quase não fizemos reordenações; ainda assim, espero que alguma noção de como a PL pode ser usada tenha transparecido.

Com alguma sorte, será possível trazer mais pessoas para a programação letrada se adotarmos uma marcação mais simples. Isso é essencial se queremos ter alguma chance de encontrar boas fórmulas para exposição de programas.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment