Bom pessoal, eu fiz apenas um semestre de Ciência da computação e eu estudei o bastante sobre Números Primos e irei fazer aqui um Algoritmo para Cálculo de Números Primos. O principal motivo de eu criar este tutorial é que fiquei muito tempo pesquisando sobre o assunto nos fórums aí a fora... Encontrei várias informaçõeszinhas que agora vou reunir, organizar e disponibilizar.
Claro que este algoritmo não é dos melhores, atualmente existem grandes pesquisas para descobrir números primos cada vez maiores com algoritmos muito especializados e complexos que rodam em super computadores, mas para nós ilustrarmos todo esse contexto dos números primos e seu envolvimento com computação nós vamos fazer aqui um algoritmo até que bastante otimizado, incluindo algums teoremas e dicas que eu aprendi por aí.
Primeiro de tudo: Para que calcular números primos? Bom, pela matemática básica nós podemos lembrar que com eles poderemos fatorar os números compostos, por exemplo:
9 = 3.3
12 = 2.2.3
15 = 3.5
Outro ponto especial é a criptografia! Os números primos, conforme aumentam, aumentam as proteções criptográficas que combinam eles criando uma espécies de "chaves". Para isso, é necessário descobrir números primos. Se o número primo for muito pequeno, facilmente será "quebrado" por meio de outros algoritmos feitos para isso. Um sistema famoso é o RSA. Que é usado na internet a todo momento, de tal modo que fica extremamente difícil alguém capturar os pacotes de uma transmissão https por exemplo e saber o número do cartão de crédito de uma pessoa que usa online banking. A segurança está no fato de que não existem algoritmos eficientes de fatoração de números. O tempo que demoraria para tal coisa ser feita a torna inviável, pois até esse tempo passar a pessoa já trocou seu cartão, o banco já trocou a chave criptográfica (o que é MUITO provável), etc...
Voltando ao ponto do algoritmo para cálculo de números primos, é interessante pensar sobre os números primos. Existem números primos e compostos. Um número é primo quando pode ser escrito por multiplicações outros inteiros. (Logo observaremos que esses inteiros SEMPRE são primos, pois todo composto pode ser decomposto em primos).
Por exemplo:
12 = 2.2.3
Você poderia dizer: 12 também pode ser escrito como 4.3 !
E eu digo: Sim, é verdade, mas 4 é um composto que pode ser escrito como 2.2 !
Ou seja: Todo número que possa ser decomposto em primos inteiros é composto, o número que não puder ser decomposto é primo.
Considere o número 11 por exemplo!
11 = ?
O 11 não pode ser decomposto por primos inteiros, logo é primo.
Agora já percebemos o que é um número primo, e sabemos que números primos não podem ser decompostos em outros inteiros e também sabemos que isso é importante para criptografia.
Agora vem a pergunta: Mas, algoritmicamente, como vou saber se um número é primo?
Essa solução é bem simples, você adota um número começando do 2 por exemplo, e verifica entre 1 e 2 se algum deles pode "dividir completamente" o número 2.
Eu disse "dividir completamente" porque eu quero dizer uma divisão que não deixe resto, ou seja, uma divisão com resto igual a zero.
Porque isso? Simples, por causa que, se um número n, por exemplo, fosse ser "dividido completamente" pelo número 2, ele é um número composto, e um de seus fatores é o 2.
Digamos assim:
(n = 46, por exemplo)
46 / 2 -> É uma divisão com resto 0
46 / 2 = 23
Portanto, 46 = 2 . 23
E como pensamos antes, todo número que puder ser decomposto em outros inteiros(primos) é composto (não-primo).
Por fim, um algoritmo básico de verificação de números primos faria o seguinte: Testaria o tal número n, desde o número 2 até o número (n-1), procurando por alguma decomposição, e caso o número seje divisível (uma divisão com resto 0) portanto o número é composto.
Ficaria mais ou menos assim:
int n, i;
int primo;
primo = 1; // Supomos que ele seja primo, e verificaremos todos os fatores de 2 até (n-1), para ver se algum deles consegue "dividir com resto 0" o nosso número n.
// Se algum número desse intervalo conseguir dividir, não precisamos mais fazer os testes, pois o número é composto. Por isso existe o comando "break", // que encerra o laço for imediatamente.
for( i = 2; i <= (n-1); i++){
if (n % i == 0){
primo = 0;
break;
}
}
if( primo) printf("Este numero %d é primo\n",n);
else printf("Este numero %d é composto\n",n);
Esse algoritmo acima é só um trecho de um programa para detectar se um dado número n é primo ou composto, ele possui alguma deficiência em otimização, iremos expor o algoritmo completo e aprimorado logo abaixo.
Para nós otimizarmos nosso algoritmo, precisaremos recorrer a uma regra da Teoria dos Números, pelo menos essa é o nome da matéria onde eu aprendi esse teorema, espero que vocês colegas também estejam vendo ou já viram essa parte da matéria, para assim entenderem melhor.
Tem um teorema importante para a otimização do nosso algoritmo:
Ele diz assim: "Todo composto tem pelo menos um fator menor ou igual a raiz quadrada dele !"
O que diz isso afinal? Diz que todo número composto (ou seja, aquele que pode ser decomposto) pode ser decomposto e que PELO MENOS UM de seus fatores TEM QUE ESTAR entre o intervalo que corresponde 2 até a raiz_quadrada_do_número.
Se você parar para pensar o que foi dito até aqui, mas precisa se esforçar em pensar mesmo, entenderá que a lógica é muito simples !
Por exemplo: Considere o número composto 25 (n = 25)
25 pode ser decomposto em fatores primos, nós saberemos que 25 = 5 . 5 onde 5 é o fator primo que aparece duas vezes.
Como sabemos que a raiz quadrada de 25 é 5, podemos pensar que se eu trabalhasse com o 6, 7, 8, 9, 10, ..., 24 nunca alcançaria o 25, porque se eu multiplicar entre esses números somente (esse conjunto que vai desde o 6 até o 24) nunca poderá dar 25, porque o menor deles (o 6) multiplicado novamente pelo menor deles (o 6 novamente) dará 36 (6x6 = 36). Isso é meio óbvio, porque se 25 = 5x5 como poderá ser escrito com a multiplicação de números começando do 6 ?
Okay, não é possível utilizar somente como fatores multiplicadores os números maiores que a raiz quadrada de n.
Mas nós podemos fazer isso: Tome como exemplo o composto 100.
Ele pode ser escrito com valores maior do que 10 (raiz quadrada de 100) :
100 = 5 x 20
100 = 2 x 50
Mas aí é que tá, os fatores maiores que raiz quadrada de n existe, mas eles DEPENDEM DOS OUTROS, e esses outros PRECISAM SER menores do que raiz quadrada de n, senão aconteçe o que vimos ali encima.
Okay, agora sabemos que para detectar um número primo basta pesquisar no intervalo que vai (de 2 até n-1) à procura de fatores em que eles "dividem completamente" o dado número primo. Se esse número existir, já era, ele é composto.
Agora também sabemos que pelo menos um desses fatores vai estar entre (2 <= x <= raiz_quadrada_de_n), portanto nós não precisariamos calcular para 2 <= n-1, mas apenas de 2 até <= raiz_quadrada_de_n.
Aprimorando nosso algoritmo, fica:
#include <stdio.h>
#include <math.h>
int n, i; // n é o número a ser verificado se "é primo" ou "é composto". No caso aqui falta uma função para ler o valor de n, como: scanf("%d",&n);
// Deixamos essa parte para voce implementar como achar necessário
int primo;
int raizQuadradadeN;
primo = 1; // Supomos que ele seja primo, e verificaremos todos os fatores de 2 até (n-1), para ver se algum deles consegue "dividir com resto 0" o nosso número n.
// Se algum número desse intervalo conseguir dividir, não precisamos mais fazer os testes, pois o número é composto. Por isso existe o comando "break", // que encerra o laço for imediatamente.
raizQuadradadeN = sqrt(n);
for( i = 2; i <= raizQuadradadeN; i++){
if (n % i == 0){
primo = 0;
break;
}
}
if( primo) printf("Este numero %d é primo\n",n);
else printf("Este numero %d é composto\n",n);
Eu adicionei agora a biblioteca math.h, para usar a função sqrt(); Talvez seja necessário algums comandos especiais na hora de compilar, dependendo do ambiente utilizado. No Dev-C++ não é necessário fazer nada, a não ser incluir esta biblioteca math.h no começo do arquivo !
Muito bem! Nossas idéias algorítmicas já estão muito boas, agora darei uma pequena observação quanto ao operador "%" (resto de divisão).
O operador % custa "meio caro" em termos de processamento... Em algumas plataformas ele realmente não agrada pela performace, por isso existe um "truque" para ser usado na linguagem C para sair "mais barato" em questão de processamento.
Observe a instrução abaixo:
if (n % i == 0)
Ela corresponde ao mesmo que a seguinte instrução:
if( (n/i) * i == n )
Porque a primeira pergunta se o resto da divisão de n por i é igual a zero, ou seja: Se n pode ser "completamente dividido" em i partes, sem sobrar nenhum resto.
E a segunda expressão pergunta a mesma coisa, só que de maneira diferente, vamos dividir por etapas para entender melhor... A parte estudada a cada caso está sublinhada em azul.
if( (n/i) * i == n )
Aqui o compilador de C irá dividir n por i de forma inteira, assim se n/i na verdade der um valor quebrado, ele arredondará para um valor inteiro (normalmente para menor).
Então, CASO n/i REALMENTE resulta em um inteiro, quer dizer então que o resto da divisão de n por i é igual a zero, não é não? Porque se um número é "completamente dividido" isso quer dizer que seu resto de divisão pelo outro é igual a zero.
Certo! CASO n/i REALMENTE resulte em um inteiro, quer dizer que n % i == 0, mas como vamos verificar se ele resultou em um inteiro ? Isso é bem simples, multiplicamos ele novamente por i e perguntamos se é igual a n. De fato é fácil de você perceber que um número dividido por i e logo em seguida multiplicado por i dará como resultado o número original, mas como a linguagem C "arredonda" o valor n/i que é calculado primeiro porque "está em parênteses", o custo de processamento sai bem baixo. Essa é a grande jogada e caso você sinta necessidade pode testar separadamente para verificar se o que foi dito aqui é verdade.
Pronto, agora eu sei que posso trocar:
if (n % i == 0)
por:
if( (n/i) * i == n )
Até este ponto eu já fiz duas otimizações para um bom algorítmo de calculo de números primos:
- O teorema
- A operação %
Na próxima edição eu espero ainda apresentar:
- Considerando somente números primos no laço (porque os compostos se decompoem apenas em primos, é bobagem testar com 2 e depois com o 4, com o 6, por exemplo.)
- Salvando os resultados num arquivo .txt para sempre voltar aonde estava e salvar seus avanços
Para ajudar na inspiração de vocês, vou por aqui o programa pronto para o cálculo de primos e direi a vocês como rodá-lo !
O código fonte do arquivo:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <math.h>
typedef int boolean;
#define true 1
#define false 0
// Este programa começa escrevendo números primos em um arquivo e não para mais.
// É doido por números primos !
// Rafael Kendy Arakaki - 06/2010
/* Variáveis Globais */
FILE* escrita;
/* Funções */
void CarregaDados( unsigned vetor[], unsigned* numeroDePrimos, unsigned *lastPrimo );
void SalvaDados( unsigned vetor[], unsigned numeroDePrimos, unsigned *numPrimosSalvos );
int main(void){
/* Declaração das variáveis */
unsigned *vetPrimos = (unsigned int*) malloc( 1000000 * sizeof(unsigned int) );
unsigned lastPrimo, numPrimos = 0;
unsigned i, possivelFator, n, sqrtN;
boolean primo;
unsigned numPrimosSalvos;
if(!vetPrimos){
printf("Erro com alocacao da memoria.\n");
}
// Passo 1 - Carrega os dados
CarregaDados( vetPrimos, &numPrimos, &lastPrimo );
numPrimosSalvos = numPrimos;
// Passo 2 - Abre a conexão append
escrita = fopen ("primos.txt", "a");
// Passo 3.1 - Processa
// considerando o número n a ser examinado se é primo ou não
//aqui aumenta de dois em dois
for( n = lastPrimo+2; numPrimos < 100000; n+=2 ){
// Considerando n o número a ser analisado e sqrtN a raiz quadrada sua.
// "i" o índice do vetor onde contêm os primos
//(***
sqrtN = (unsigned int) sqrt(n);
i = 0;
possivelFator = vetPrimos[i];
primo = true; // Supondo que seja primo.
while( possivelFator <= sqrtN )
{
// Verificar se é composto (ou seja, não-primo).
if( (n/possivelFator) * possivelFator == n )
{
primo = false;
break;
}
possivelFator = vetPrimos[++i];
}
if(primo){
vetPrimos[numPrimos] = n;
numPrimos++;
printf("%u\n",n);
}
//***) Saída: numero de numerosPrimos atualizado, atualização do vetor, printf do numero.
}
// Passo 3.2 - Salva
SalvaDados (vetPrimos, numPrimos, &numPrimosSalvos );
// Passo 3.3 - Salva tudo e fecha a conexão append e o programa todo
fclose(escrita);
printf("Processo completado. Foram processados %d primos",numPrimos);
getch();
return 0;
}
// é um vetor de unsigneds ints !
void CarregaDados( unsigned lista[], unsigned* numeroDePrimos, unsigned *lastPrimo ) {
FILE* leitura;
unsigned n, count = 0;
leitura = fopen ("primos.txt", "r");
if(!leitura){
printf("Erro no carregamento do arquivo.");
exit(100);
}
else{
// Carregar os dados
while( fscanf(leitura," %u", &n) != EOF ){
lista[count] = n;
count++;
}
}
*lastPrimo = n;
*numeroDePrimos = count;
fclose(leitura);
return;
}
// Salva os dados a partir da última vez quando ele salvou.
// Preciso do índice,
void SalvaDados( unsigned lista[], unsigned numeroPrimos, unsigned *numPrimosSalvos) {
static int pulaLinha = 0;
for (; *numPrimosSalvos < numeroPrimos; (*numPrimosSalvos)++)
{
if( pulaLinha++ % 10 == 0 ) fprintf(escrita,"%u\n",lista[*numPrimosSalvos]);
else fprintf(escrita,"%u ",lista[*numPrimosSalvos]);
}
}
/* Este projeto:
Baseia-se no conceito de que a memória RAM é muito mais rápida que o carregamento de dados de textos (HD), assim sendo...
--O programa se separaria em três partes:
-Carregamento de números primos
-Processamento dos números primos novos (com base nos que já existem)
-Salvar todos os números primos.
obs: Outro ponto importante para o projeto é utilizar o teorema de que devemos percorrer somente até o i for menor ou igual que sqrt(n) e não até menor que n. (a busca de fatores)
obs2: Outro ponto importante é em relação ao cálculo com % ou então método: "(n / i) * i == n ?" = "n % i == 0 ?" este segundo aparenta ser bem mais rápido.
obs3: Vamos fazer o loop andar de 2 em dois começando do 3 (a busca de primos).
Pelo menos um dos fatores primos é = ou < que raiz de n !!!!!!!!!!
Sendo assim esse n dividido por esse fator sempre vai dar um número inteiro. (compostos)
COMPLETADO! Em 24/06/2010 ás 15:46 =)
TODO:
-Ainda não conheço outro método para melhorar o desempenho do algoritmo, se alguém conheçer poderia entrar em contato comigo para que eu melhorasse nosso algoritmo :P
-De fato esse algoritmo está muito distante dos melhores existentes no planeta, mas é bom já e muito interessante, porque é mais rápido que 80% dos encontrados na internet... Você pode calcular os 1.000.000 primeiros números primos num piscar de olhos
*/
obs: usuários do gcc talvez seja necessário retirar a biblioteca conio.h e também o comando getch(), mas eles não terão problema algum porque para eles (linux) é desnecessário o comando getch().
Salve e compile este programa, e junto dele crie um arquivo .txt (isso mesmo, deve ser .txt, aquele do bloco de notas do winXP!)
E agora digite neste bloco de notas: "2<blank>3<blank>"(IGNORE AS ASPAS) (CONSIDERE <BLANK> COMO UM ESPAÇO EM BRANCO!!!!)
Entendeu? Precisa escrever o número 2 e dar um espaço em branco e depois digitar o número 3 e dar outro espaço em branco.
E deve-se salvar o nome do arquivo como primos.txt , tudo minúsculo conforme escrito aqui! Senão o programa não irá funcionar.
Para aumentar o número de primos a serem procurados, deve-se mudar aqui:
for( n = lastPrimo+2; numPrimos < 100000; n+=2 ){
É só mudar o 100.000 para a quantidade de primos que você quer deixar que o programa encontre, cuidado para não exagerar, pois quanto maiores vai ficando os números mais difícil é testar todas as combinações de seus antecessores primos menores que raiz quadrada dele próprio (ufa!).
É isso galera! Testem aí, leiam se puderem e me digam o que acharam... Se alguém não leu porque não entendeu uma parte, porque achou muito extenso ou qualquer coisa fala aí também para o caso de uma melhoria. Qualquer erro também avise e queria dizer que quando eu escrevi esse texto já estava com um pouco de sono então podem haver muitos erros (principalmente de gramática, concordância... de pontuação nem se fala então :wacko: ).
Se alguém gostar eu pensaria em continuar o tutorial até chegarmos ... até onde for possivel :blush:
EDIT 27/07/2010:
Como eu prometi, irei continuar o tutorial para entendermos todas as partes do algoritmo:
Considerando somente números primos no laço
Como já vimos, segue a definição de número composto e número primo:
Composto: É aquele que pode ser divisível (resto da divisão == 0) por outro número inteiro sem ser ele próprio ou o 1. (4, 6, 8, 9, 10...)
Primo: É aquele que não pode ser divisível (resto da divisão == 0) por outro inteiro sem ser ele próprio ou o 1. (Exemplos: 2, 3, 5, ...)
Vamos enumerar de 1 até 20, quais são os primos e quais são os compostos:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Assim sendo, vamos mostrar porque os compostos são compostos:
4 = 2.2
6 = 2.3
8 = 2.2.2
9 = 3.3
10 = 2.5
12 = 2.2.3
14 = 2.7
15 = 3.5
16 = 2.2.2.2
18 = 2.3.3
20 = 2.2.5
Poderíamos notar que todos esses números compostos sempre se decompõe em primos! Não só são divisíveis (resto de divisão == 0) por um número no meio entre 1 e ele mesmo (1 < x < n), como também sempre serão divisíveis por primos (1 < primos < n).
Agora voltando ao nosso algoritmo em construção, que até agora é esse aqui:
#include <stdio.h>
#include <math.h>
int n, i; // n é o número a ser verificado se "é primo" ou "é composto". No caso aqui falta uma função para ler o valor de n, como: scanf("%d",&n);
// Deixamos essa parte para voce implementar como achar necessário
int primo;
int raizQuadradadeN;
primo = 1; // Supomos que ele seja primo, e verificaremos todos os fatores de 2 até (n-1), para ver se algum deles consegue "dividir com resto 0" o nosso número n.
// Se algum número desse intervalo conseguir dividir, não precisamos mais fazer os testes, pois o número é composto. Por isso existe o comando "break", // que encerra o laço for imediatamente.
raizQuadradadeN = sqrt(n);
for( i = 2; i <= raizQuadradadeN; i++){
if (n % i == 0){
primo = 0;
break;
}
}
if( primo) printf("Este numero %d é primo\n",n);
else printf("Este numero %d é composto\n",n);
Nós podemos melhorar ele! Pois no loop onde o i começa a partir do 2 e vai até <= Raiz Quadrada De N. Ele faz essa comparação com todos os números, porém isso absolutamente não é necessário. Nós só precisamos comparar com os números primos que se situam entre 1 e <= Raiz Quadrada De N.
Começe a pensar sobre isso: "Precisamos testar apenas os números primos entre 1 e raiz quadrada de N para descobrir se determinado número é primo ou não !" Pensando deste modo, você irá, então, precisar de todos os números primos do mundo na sua memória, o que é uma redundância. A grande jogada do esquema, é que você primeiro vai descobrindo os números primos desde o 2, 3, 5... e vai armazenando-os em um vetor na memória, para assim ir descobrindo outros maiores.
Claro, você poderia dizer: "Pra que fazer isso? Vamos fazer como estamos fazendo, testando de 1 em 1 até alcançar Raiz Quadrada de N !"
Então eu digo: "Mas como estamos focando na otimização, a partir de determinado número, nós teremos muitos números para verificar... Se considerarmos apenas os números primos no loop o número de testes necessários diminui assombrosamente."
Ou seja, aqui você já pode fazer a seguinte conclusão: Existem dois tipos de algoritmos que testam números primos, aqueles que já conheçem todos os números primos antecedentes ao número que se está testando (n) (algoritmo mais rápido), e aquele que não conheçe aboslutamente nenhum número primo mas mesmo assim descobre (nosso atual algoritmo).
Vamos às otimizações!
Primeira coisa que sabemos, é que teremos que guardar em um vetor os números primos... Precisamos calcular os números primos e logo em seguida guardá-los no vetor.
Segunda coisa é que nós não precisamos mais testar todos os números antecedentes à raiz Quadrada de N e sim apenas os primos que são antecedentes à raiz Quadrada de N, e os primos estarão todos guardados em nosso vetor de primos, que chamaremos no algoritmo a seguir de vetPrimos.
Nós poderemos fazer algo assim então:
#include <stdio.h>
#include <math.h>
#include <conio.h>
typedef char boolean;
#define true 1
#define false 0
int main(){
int n, raizQuadradaDeN, i;
int limite;
boolean primo;
printf("Digite o limite do algoritmo, ate qual numero devemos selecionar se é primo ou não!\n");
scanf("%d",&limite);
// Com base no limite, criaremos o vetor que armazena primos
int vetPrimos[limite];
int numPrimos = 0; // Essa variável sempre cresce quando o número de primos aumenta.
// Adicionamos o número 2 manualmente no vetor e aumentamos o numPrimos.
vetPrimos[0] = 2;
numPrimos++;
// Vamos começar a procurar números a partir de n = 3.
for( n = 3; n <= limite; n++){
raizQuadradaDeN = (int) sqrt(n); // sqrt() é uma função que retorna a raiz quadrada do número, vem da biblioteca <math.h>
// Como sqrt() retorna float, é importante utilizar o (int) na frente dela, para não dar warning.
primo = true; // Supomos que o numero é primo, se detectarmos que ele é composto, mudamos essa variavel para false.
for( i = 0; vetPrimos[i] <= raizQuadradaDeN; i++){
// Agora aqui temos uma novidade! Não iremos mais comparar o "i" simplesmente.
// Agora o "i" nada mais é do que o índice do vetPrimos, que vai aumentando a cada laço...
// Conforme o "i" aumenta, os valores que estão no vetPrimos também aumenta...
// Pois vão sendo selecionados os primos maiores.
// Se você entender essas linhas do programa você entendeu tudo ! (Se necessário crie algums
// printfs para você entender melhor ).
if( (n/vetPrimos[i]) * vetPrimos[i] == n ){ // mesmo valor que "n % vetPrimos[i] == 0"
primo = false;
break; // Sai do laço rapidamente.
}
}
if( primo){
printf("%d é primo\n",n);
vetPrimos[numPrimos] = n;
numPrimos++;
}
else printf("%d é composto\n",n);
}
getch();
}
E este foi o edit de hoje, com este algoritmo já estamos com quase todas as otimizações feitas. Falta apenas:
- Salvando os resultados num arquivo .txt para sempre voltar aonde estava e salvar seus avanços
Pergunta
Rafael K. Arakaki
Bom pessoal, eu fiz apenas um semestre de Ciência da computação e eu estudei o bastante sobre Números Primos e irei fazer aqui um Algoritmo para Cálculo de Números Primos. O principal motivo de eu criar este tutorial é que fiquei muito tempo pesquisando sobre o assunto nos fórums aí a fora... Encontrei várias informaçõeszinhas que agora vou reunir, organizar e disponibilizar.
Claro que este algoritmo não é dos melhores, atualmente existem grandes pesquisas para descobrir números primos cada vez maiores com algoritmos muito especializados e complexos que rodam em super computadores, mas para nós ilustrarmos todo esse contexto dos números primos e seu envolvimento com computação nós vamos fazer aqui um algoritmo até que bastante otimizado, incluindo algums teoremas e dicas que eu aprendi por aí.
Primeiro de tudo: Para que calcular números primos? Bom, pela matemática básica nós podemos lembrar que com eles poderemos fatorar os números compostos, por exemplo:
Outro ponto especial é a criptografia! Os números primos, conforme aumentam, aumentam as proteções criptográficas que combinam eles criando uma espécies de "chaves". Para isso, é necessário descobrir números primos. Se o número primo for muito pequeno, facilmente será "quebrado" por meio de outros algoritmos feitos para isso. Um sistema famoso é o RSA. Que é usado na internet a todo momento, de tal modo que fica extremamente difícil alguém capturar os pacotes de uma transmissão https por exemplo e saber o número do cartão de crédito de uma pessoa que usa online banking. A segurança está no fato de que não existem algoritmos eficientes de fatoração de números. O tempo que demoraria para tal coisa ser feita a torna inviável, pois até esse tempo passar a pessoa já trocou seu cartão, o banco já trocou a chave criptográfica (o que é MUITO provável), etc...Voltando ao ponto do algoritmo para cálculo de números primos, é interessante pensar sobre os números primos. Existem números primos e compostos. Um número é primo quando pode ser escrito por multiplicações outros inteiros. (Logo observaremos que esses inteiros SEMPRE são primos, pois todo composto pode ser decomposto em primos).
Por exemplo:
12 = 2.2.3
Você poderia dizer: 12 também pode ser escrito como 4.3 !
E eu digo: Sim, é verdade, mas 4 é um composto que pode ser escrito como 2.2 !
Ou seja: Todo número que possa ser decomposto em primos inteiros é composto, o número que não puder ser decomposto é primo.
Considere o número 11 por exemplo!
11 = ?
O 11 não pode ser decomposto por primos inteiros, logo é primo.
Mais informações sobre números primos aqui.
Agora já percebemos o que é um número primo, e sabemos que números primos não podem ser decompostos em outros inteiros e também sabemos que isso é importante para criptografia.
Agora vem a pergunta: Mas, algoritmicamente, como vou saber se um número é primo?
Essa solução é bem simples, você adota um número começando do 2 por exemplo, e verifica entre 1 e 2 se algum deles pode "dividir completamente" o número 2.
Eu disse "dividir completamente" porque eu quero dizer uma divisão que não deixe resto, ou seja, uma divisão com resto igual a zero.
Porque isso? Simples, por causa que, se um número n, por exemplo, fosse ser "dividido completamente" pelo número 2, ele é um número composto, e um de seus fatores é o 2.
Digamos assim:
E como pensamos antes, todo número que puder ser decomposto em outros inteiros(primos) é composto (não-primo).
Por fim, um algoritmo básico de verificação de números primos faria o seguinte: Testaria o tal número n, desde o número 2 até o número (n-1), procurando por alguma decomposição, e caso o número seje divisível (uma divisão com resto 0) portanto o número é composto.
Ficaria mais ou menos assim:
int n, i; int primo; primo = 1; // Supomos que ele seja primo, e verificaremos todos os fatores de 2 até (n-1), para ver se algum deles consegue "dividir com resto 0" o nosso número n. // Se algum número desse intervalo conseguir dividir, não precisamos mais fazer os testes, pois o número é composto. Por isso existe o comando "break", // que encerra o laço for imediatamente. for( i = 2; i <= (n-1); i++){ if (n % i == 0){ primo = 0; break; } } if( primo) printf("Este numero %d é primo\n",n); else printf("Este numero %d é composto\n",n);Esse algoritmo acima é só um trecho de um programa para detectar se um dado número n é primo ou composto, ele possui alguma deficiência em otimização, iremos expor o algoritmo completo e aprimorado logo abaixo. Para nós otimizarmos nosso algoritmo, precisaremos recorrer a uma regra da Teoria dos Números, pelo menos essa é o nome da matéria onde eu aprendi esse teorema, espero que vocês colegas também estejam vendo ou já viram essa parte da matéria, para assim entenderem melhor. Tem um teorema importante para a otimização do nosso algoritmo: Ele diz assim: "Todo composto tem pelo menos um fator menor ou igual a raiz quadrada dele !" O que diz isso afinal? Diz que todo número composto (ou seja, aquele que pode ser decomposto) pode ser decomposto e que PELO MENOS UM de seus fatores TEM QUE ESTAR entre o intervalo que corresponde 2 até a raiz_quadrada_do_número. Se você parar para pensar o que foi dito até aqui, mas precisa se esforçar em pensar mesmo, entenderá que a lógica é muito simples ! Por exemplo: Considere o número composto 25 (n = 25) 25 pode ser decomposto em fatores primos, nós saberemos que 25 = 5 . 5 onde 5 é o fator primo que aparece duas vezes. Como sabemos que a raiz quadrada de 25 é 5, podemos pensar que se eu trabalhasse com o 6, 7, 8, 9, 10, ..., 24 nunca alcançaria o 25, porque se eu multiplicar entre esses números somente (esse conjunto que vai desde o 6 até o 24) nunca poderá dar 25, porque o menor deles (o 6) multiplicado novamente pelo menor deles (o 6 novamente) dará 36 (6x6 = 36). Isso é meio óbvio, porque se 25 = 5x5 como poderá ser escrito com a multiplicação de números começando do 6 ? Okay, não é possível utilizar somente como fatores multiplicadores os números maiores que a raiz quadrada de n. Mas nós podemos fazer isso: Tome como exemplo o composto 100. Ele pode ser escrito com valores maior do que 10 (raiz quadrada de 100) : 100 = 5 x 20 100 = 2 x 50 Mas aí é que tá, os fatores maiores que raiz quadrada de n existe, mas eles DEPENDEM DOS OUTROS, e esses outros PRECISAM SER menores do que raiz quadrada de n, senão aconteçe o que vimos ali encima. Okay, agora sabemos que para detectar um número primo basta pesquisar no intervalo que vai (de 2 até n-1) à procura de fatores em que eles "dividem completamente" o dado número primo. Se esse número existir, já era, ele é composto. Agora também sabemos que pelo menos um desses fatores vai estar entre (2 <= x <= raiz_quadrada_de_n), portanto nós não precisariamos calcular para 2 <= n-1, mas apenas de 2 até <= raiz_quadrada_de_n. Aprimorando nosso algoritmo, fica:#include <stdio.h> #include <math.h> int n, i; // n é o número a ser verificado se "é primo" ou "é composto". No caso aqui falta uma função para ler o valor de n, como: scanf("%d",&n); // Deixamos essa parte para voce implementar como achar necessário int primo; int raizQuadradadeN; primo = 1; // Supomos que ele seja primo, e verificaremos todos os fatores de 2 até (n-1), para ver se algum deles consegue "dividir com resto 0" o nosso número n. // Se algum número desse intervalo conseguir dividir, não precisamos mais fazer os testes, pois o número é composto. Por isso existe o comando "break", // que encerra o laço for imediatamente. raizQuadradadeN = sqrt(n); for( i = 2; i <= raizQuadradadeN; i++){ if (n % i == 0){ primo = 0; break; } } if( primo) printf("Este numero %d é primo\n",n); else printf("Este numero %d é composto\n",n);Eu adicionei agora a biblioteca math.h, para usar a função sqrt(); Talvez seja necessário algums comandos especiais na hora de compilar, dependendo do ambiente utilizado. No Dev-C++ não é necessário fazer nada, a não ser incluir esta biblioteca math.h no começo do arquivo ! Muito bem! Nossas idéias algorítmicas já estão muito boas, agora darei uma pequena observação quanto ao operador "%" (resto de divisão). O operador % custa "meio caro" em termos de processamento... Em algumas plataformas ele realmente não agrada pela performace, por isso existe um "truque" para ser usado na linguagem C para sair "mais barato" em questão de processamento. Observe a instrução abaixo: Ela corresponde ao mesmo que a seguinte instrução: Porque a primeira pergunta se o resto da divisão de n por i é igual a zero, ou seja: Se n pode ser "completamente dividido" em i partes, sem sobrar nenhum resto. E a segunda expressão pergunta a mesma coisa, só que de maneira diferente, vamos dividir por etapas para entender melhor... A parte estudada a cada caso está sublinhada em azul. if( (n/i) * i == n ) Aqui o compilador de C irá dividir n por i de forma inteira, assim se n/i na verdade der um valor quebrado, ele arredondará para um valor inteiro (normalmente para menor). Então, CASO n/i REALMENTE resulta em um inteiro, quer dizer então que o resto da divisão de n por i é igual a zero, não é não? Porque se um número é "completamente dividido" isso quer dizer que seu resto de divisão pelo outro é igual a zero. Certo! CASO n/i REALMENTE resulte em um inteiro, quer dizer que n % i == 0, mas como vamos verificar se ele resultou em um inteiro ? Isso é bem simples, multiplicamos ele novamente por i e perguntamos se é igual a n. De fato é fácil de você perceber que um número dividido por i e logo em seguida multiplicado por i dará como resultado o número original, mas como a linguagem C "arredonda" o valor n/i que é calculado primeiro porque "está em parênteses", o custo de processamento sai bem baixo. Essa é a grande jogada e caso você sinta necessidade pode testar separadamente para verificar se o que foi dito aqui é verdade. Pronto, agora eu sei que posso trocar: por: Até este ponto eu já fiz duas otimizações para um bom algorítmo de calculo de números primos: - O teorema - A operação % Na próxima edição eu espero ainda apresentar: - Considerando somente números primos no laço (porque os compostos se decompoem apenas em primos, é bobagem testar com 2 e depois com o 4, com o 6, por exemplo.) - Salvando os resultados num arquivo .txt para sempre voltar aonde estava e salvar seus avanços Para ajudar na inspiração de vocês, vou por aqui o programa pronto para o cálculo de primos e direi a vocês como rodá-lo ! O código fonte do arquivo:#include <stdio.h> #include <conio.h> #include <stdlib.h> #include <math.h> typedef int boolean; #define true 1 #define false 0 // Este programa começa escrevendo números primos em um arquivo e não para mais. // É doido por números primos ! // Rafael Kendy Arakaki - 06/2010 /* Variáveis Globais */ FILE* escrita; /* Funções */ void CarregaDados( unsigned vetor[], unsigned* numeroDePrimos, unsigned *lastPrimo ); void SalvaDados( unsigned vetor[], unsigned numeroDePrimos, unsigned *numPrimosSalvos ); int main(void){ /* Declaração das variáveis */ unsigned *vetPrimos = (unsigned int*) malloc( 1000000 * sizeof(unsigned int) ); unsigned lastPrimo, numPrimos = 0; unsigned i, possivelFator, n, sqrtN; boolean primo; unsigned numPrimosSalvos; if(!vetPrimos){ printf("Erro com alocacao da memoria.\n"); } // Passo 1 - Carrega os dados CarregaDados( vetPrimos, &numPrimos, &lastPrimo ); numPrimosSalvos = numPrimos; // Passo 2 - Abre a conexão append escrita = fopen ("primos.txt", "a"); // Passo 3.1 - Processa // considerando o número n a ser examinado se é primo ou não //aqui aumenta de dois em dois for( n = lastPrimo+2; numPrimos < 100000; n+=2 ){ // Considerando n o número a ser analisado e sqrtN a raiz quadrada sua. // "i" o índice do vetor onde contêm os primos //(*** sqrtN = (unsigned int) sqrt(n); i = 0; possivelFator = vetPrimos[i]; primo = true; // Supondo que seja primo. while( possivelFator <= sqrtN ) { // Verificar se é composto (ou seja, não-primo). if( (n/possivelFator) * possivelFator == n ) { primo = false; break; } possivelFator = vetPrimos[++i]; } if(primo){ vetPrimos[numPrimos] = n; numPrimos++; printf("%u\n",n); } //***) Saída: numero de numerosPrimos atualizado, atualização do vetor, printf do numero. } // Passo 3.2 - Salva SalvaDados (vetPrimos, numPrimos, &numPrimosSalvos ); // Passo 3.3 - Salva tudo e fecha a conexão append e o programa todo fclose(escrita); printf("Processo completado. Foram processados %d primos",numPrimos); getch(); return 0; } // é um vetor de unsigneds ints ! void CarregaDados( unsigned lista[], unsigned* numeroDePrimos, unsigned *lastPrimo ) { FILE* leitura; unsigned n, count = 0; leitura = fopen ("primos.txt", "r"); if(!leitura){ printf("Erro no carregamento do arquivo."); exit(100); } else{ // Carregar os dados while( fscanf(leitura," %u", &n) != EOF ){ lista[count] = n; count++; } } *lastPrimo = n; *numeroDePrimos = count; fclose(leitura); return; } // Salva os dados a partir da última vez quando ele salvou. // Preciso do índice, void SalvaDados( unsigned lista[], unsigned numeroPrimos, unsigned *numPrimosSalvos) { static int pulaLinha = 0; for (; *numPrimosSalvos < numeroPrimos; (*numPrimosSalvos)++) { if( pulaLinha++ % 10 == 0 ) fprintf(escrita,"%u\n",lista[*numPrimosSalvos]); else fprintf(escrita,"%u ",lista[*numPrimosSalvos]); } } /* Este projeto: Baseia-se no conceito de que a memória RAM é muito mais rápida que o carregamento de dados de textos (HD), assim sendo... --O programa se separaria em três partes: -Carregamento de números primos -Processamento dos números primos novos (com base nos que já existem) -Salvar todos os números primos. obs: Outro ponto importante para o projeto é utilizar o teorema de que devemos percorrer somente até o i for menor ou igual que sqrt(n) e não até menor que n. (a busca de fatores) obs2: Outro ponto importante é em relação ao cálculo com % ou então método: "(n / i) * i == n ?" = "n % i == 0 ?" este segundo aparenta ser bem mais rápido. obs3: Vamos fazer o loop andar de 2 em dois começando do 3 (a busca de primos). Pelo menos um dos fatores primos é = ou < que raiz de n !!!!!!!!!! Sendo assim esse n dividido por esse fator sempre vai dar um número inteiro. (compostos) COMPLETADO! Em 24/06/2010 ás 15:46 =) TODO: -Ainda não conheço outro método para melhorar o desempenho do algoritmo, se alguém conheçer poderia entrar em contato comigo para que eu melhorasse nosso algoritmo :P -De fato esse algoritmo está muito distante dos melhores existentes no planeta, mas é bom já e muito interessante, porque é mais rápido que 80% dos encontrados na internet... Você pode calcular os 1.000.000 primeiros números primos num piscar de olhos */obs: usuários do gcc talvez seja necessário retirar a biblioteca conio.h e também o comando getch(), mas eles não terão problema algum porque para eles (linux) é desnecessário o comando getch(). Salve e compile este programa, e junto dele crie um arquivo .txt (isso mesmo, deve ser .txt, aquele do bloco de notas do winXP!) E agora digite neste bloco de notas: "2<blank>3<blank>"(IGNORE AS ASPAS) (CONSIDERE <BLANK> COMO UM ESPAÇO EM BRANCO!!!!) Entendeu? Precisa escrever o número 2 e dar um espaço em branco e depois digitar o número 3 e dar outro espaço em branco. E deve-se salvar o nome do arquivo como primos.txt , tudo minúsculo conforme escrito aqui! Senão o programa não irá funcionar. Para aumentar o número de primos a serem procurados, deve-se mudar aqui:for( n = lastPrimo+2; numPrimos < 100000; n+=2 ){É só mudar o 100.000 para a quantidade de primos que você quer deixar que o programa encontre, cuidado para não exagerar, pois quanto maiores vai ficando os números mais difícil é testar todas as combinações de seus antecessores primos menores que raiz quadrada dele próprio (ufa!). É isso galera! Testem aí, leiam se puderem e me digam o que acharam... Se alguém não leu porque não entendeu uma parte, porque achou muito extenso ou qualquer coisa fala aí também para o caso de uma melhoria. Qualquer erro também avise e queria dizer que quando eu escrevi esse texto já estava com um pouco de sono então podem haver muitos erros (principalmente de gramática, concordância... de pontuação nem se fala então :wacko: ). Se alguém gostar eu pensaria em continuar o tutorial até chegarmos ... até onde for possivel :blush: EDIT 27/07/2010: Como eu prometi, irei continuar o tutorial para entendermos todas as partes do algoritmo: Considerando somente números primos no laço Como já vimos, segue a definição de número composto e número primo: Composto: É aquele que pode ser divisível (resto da divisão == 0) por outro número inteiro sem ser ele próprio ou o 1. (4, 6, 8, 9, 10...) Primo: É aquele que não pode ser divisível (resto da divisão == 0) por outro inteiro sem ser ele próprio ou o 1. (Exemplos: 2, 3, 5, ...) Vamos enumerar de 1 até 20, quais são os primos e quais são os compostos: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 Assim sendo, vamos mostrar porque os compostos são compostos: 4 = 2.2 6 = 2.3 8 = 2.2.2 9 = 3.3 10 = 2.5 12 = 2.2.3 14 = 2.7 15 = 3.5 16 = 2.2.2.2 18 = 2.3.3 20 = 2.2.5 Poderíamos notar que todos esses números compostos sempre se decompõe em primos! Não só são divisíveis (resto de divisão == 0) por um número no meio entre 1 e ele mesmo (1 < x < n), como também sempre serão divisíveis por primos (1 < primos < n). Agora voltando ao nosso algoritmo em construção, que até agora é esse aqui:#include <stdio.h> #include <math.h> int n, i; // n é o número a ser verificado se "é primo" ou "é composto". No caso aqui falta uma função para ler o valor de n, como: scanf("%d",&n); // Deixamos essa parte para voce implementar como achar necessário int primo; int raizQuadradadeN; primo = 1; // Supomos que ele seja primo, e verificaremos todos os fatores de 2 até (n-1), para ver se algum deles consegue "dividir com resto 0" o nosso número n. // Se algum número desse intervalo conseguir dividir, não precisamos mais fazer os testes, pois o número é composto. Por isso existe o comando "break", // que encerra o laço for imediatamente. raizQuadradadeN = sqrt(n); for( i = 2; i <= raizQuadradadeN; i++){ if (n % i == 0){ primo = 0; break; } } if( primo) printf("Este numero %d é primo\n",n); else printf("Este numero %d é composto\n",n);Nós podemos melhorar ele! Pois no loop onde o i começa a partir do 2 e vai até <= Raiz Quadrada De N. Ele faz essa comparação com todos os números, porém isso absolutamente não é necessário. Nós só precisamos comparar com os números primos que se situam entre 1 e <= Raiz Quadrada De N. Começe a pensar sobre isso: "Precisamos testar apenas os números primos entre 1 e raiz quadrada de N para descobrir se determinado número é primo ou não !" Pensando deste modo, você irá, então, precisar de todos os números primos do mundo na sua memória, o que é uma redundância. A grande jogada do esquema, é que você primeiro vai descobrindo os números primos desde o 2, 3, 5... e vai armazenando-os em um vetor na memória, para assim ir descobrindo outros maiores. Claro, você poderia dizer: "Pra que fazer isso? Vamos fazer como estamos fazendo, testando de 1 em 1 até alcançar Raiz Quadrada de N !" Então eu digo: "Mas como estamos focando na otimização, a partir de determinado número, nós teremos muitos números para verificar... Se considerarmos apenas os números primos no loop o número de testes necessários diminui assombrosamente." Ou seja, aqui você já pode fazer a seguinte conclusão: Existem dois tipos de algoritmos que testam números primos, aqueles que já conheçem todos os números primos antecedentes ao número que se está testando (n) (algoritmo mais rápido), e aquele que não conheçe aboslutamente nenhum número primo mas mesmo assim descobre (nosso atual algoritmo). Vamos às otimizações! Primeira coisa que sabemos, é que teremos que guardar em um vetor os números primos... Precisamos calcular os números primos e logo em seguida guardá-los no vetor. Segunda coisa é que nós não precisamos mais testar todos os números antecedentes à raiz Quadrada de N e sim apenas os primos que são antecedentes à raiz Quadrada de N, e os primos estarão todos guardados em nosso vetor de primos, que chamaremos no algoritmo a seguir de vetPrimos. Nós poderemos fazer algo assim então:#include <stdio.h> #include <math.h> #include <conio.h> typedef char boolean; #define true 1 #define false 0 int main(){ int n, raizQuadradaDeN, i; int limite; boolean primo; printf("Digite o limite do algoritmo, ate qual numero devemos selecionar se é primo ou não!\n"); scanf("%d",&limite); // Com base no limite, criaremos o vetor que armazena primos int vetPrimos[limite]; int numPrimos = 0; // Essa variável sempre cresce quando o número de primos aumenta. // Adicionamos o número 2 manualmente no vetor e aumentamos o numPrimos. vetPrimos[0] = 2; numPrimos++; // Vamos começar a procurar números a partir de n = 3. for( n = 3; n <= limite; n++){ raizQuadradaDeN = (int) sqrt(n); // sqrt() é uma função que retorna a raiz quadrada do número, vem da biblioteca <math.h> // Como sqrt() retorna float, é importante utilizar o (int) na frente dela, para não dar warning. primo = true; // Supomos que o numero é primo, se detectarmos que ele é composto, mudamos essa variavel para false. for( i = 0; vetPrimos[i] <= raizQuadradaDeN; i++){ // Agora aqui temos uma novidade! Não iremos mais comparar o "i" simplesmente. // Agora o "i" nada mais é do que o índice do vetPrimos, que vai aumentando a cada laço... // Conforme o "i" aumenta, os valores que estão no vetPrimos também aumenta... // Pois vão sendo selecionados os primos maiores. // Se você entender essas linhas do programa você entendeu tudo ! (Se necessário crie algums // printfs para você entender melhor ). if( (n/vetPrimos[i]) * vetPrimos[i] == n ){ // mesmo valor que "n % vetPrimos[i] == 0" primo = false; break; // Sai do laço rapidamente. } } if( primo){ printf("%d é primo\n",n); vetPrimos[numPrimos] = n; numPrimos++; } else printf("%d é composto\n",n); } getch(); }E este foi o edit de hoje, com este algoritmo já estamos com quase todas as otimizações feitas. Falta apenas:
- Salvando os resultados num arquivo .txt para sempre voltar aonde estava e salvar seus avanços
Até o próximo edit :blush:
Editado por Rafael K. ArakakiLink para o comentário
Compartilhar em outros sites
7 respostass a esta questão
Posts Recomendados
Participe da discussão
Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.