Código em Java que escreve no terminal todos os CPFs válidos do Brasil (para fins estritamente acadêmicos).
Comando para compilar: javac -d target/classes src/main/java/com/mycompany/cpfs/*.java
Comando para executar: java -cp target/classes com.mycompany.cpfs.Cpfs
A implementação possui um algoritmo usado para gerar CPFs feito com base em algoritmo semelhante que verifica se um dado CPF é válido ou não, sendo este usado comparando os dígitos verificadores (os dois últimos, após o traço) do CPF a ser conferido com os dígitos verificadores calculados a partir dos demais dígitos (os 9 antes do traço).
Para o cálculo do dígito verificador 1, multiplica-se o os 9 dígitos por um multiplicador que vai de 10 (que multiplica o primeiro dígito) a 2 (que multiplica o nono dígito) e os resultados são somados; digamos que tal soma seja referida como 's', que é dado por:
Na fórmula, 'i', variando de 0 a 8, faz com que '(10 - i)' varie de 10 a 2, e que 'v' seja cada item do vetor, sendo 'vi' o elemento na posição i do vetor. A soma obtida é então dividida por 11, e o resto da divisão é analisado: se o resto da divisão for menor que 2, o digito verificador 1 calculado é definido como 0 para a combinação de 9 dígitos em questão. Caso contrário, o valor atribuído ao dígito é o resto da divisão citada subtraído de 11:
O dígito verificador 2 é gerado de maneira semelhante, mas com 'i' variando de 0 a 9, pois adiciona-se ao array, antes tendo nove dígitos, o dígito verificador calculado e, assim, '(10 - i)' varia de 11 a 2.
Para gerar CPFs válidos, foram usados nove laços de repetição encapsulados para gerar todas as combinações de nove dígitos e, para cada combinação, usa-se a lógica abordada anteriormente para gerar a única (se existir) possibilidade de dígitos verificadores para cada combinação.
Além disso, é feita uma última verificação: CPFs com todos os dígitos iguais, mesmo que passem no algoritmo (como 000.000.000-00), não são válidos, e previne-se tal situação antes de exibir o CPF.
Por fim, foi usada a função que formata o CPF a ser escrito, inserindo os pontos e o traço em cada CPF:
Temos tempo constante de execução da operação principal (geração dos CPFs válidos), mas, como cada um dos 9 laços de repetição encapsulados na geração é executado 10 vezes, temos 10^9 operações referentes a cada um dos 2 dígitos verificadores, ou seja, 1.000.000.000 de operações para cada dígito verificador (2 bilhões ao todo).
for(int a = 9; b >= 0; a--){ //10 iterações
for(int b = 9; b >= 0; b--){ //10 * 10 = 100
for(int c = 9; c >=0; c--){ //10 * 10 * 10 = 1.000
...
10^9 iterações totais
Assim, conclui-se que esse tipo de implementação representa custo computacional significativamente desnecessário, mas existe valor de análise marcante acerca d