Sabemos que existem infinitos números primos. Mas, como podemos determinar se um número natural n é primo ou composto? Uma possibilidade é testar candidatos a divisores e exibir um divisor não trivial, isto é, um divisor diferente de 1 e n. Neste post nos restringimos aos divisores inteiros positivos. Mas não precisamos exaurir a lista de todos os inteiros de 2 até n-1. Podemos nos valer do Crivo de Eratóstenes. No nosso caso vamos usar um versão mais fraca.
Proposição [1] Se n é composto então existe um divisor d não trivial tal que d\leq\sqrt{n}.
Demonstração.
Suponha por absurdo que n é um número composto e que não possui divisor não trivial menor ou igual do que \sqrt{n}. Portanto, existem a,b \in \mathbb{N} tais que n=a\cdot b e a,b>1. Por outro lado, a>\sqrt{n} e b>\sqrt{n}, assim, n=a\cdot b>\sqrt{n}\cdot \sqrt{n}=n . Contradição. Logo, n possui pelo menos um divisor não trivial menor ou igual do que \sqrt{n}.\,\,\, \square
Por outro lado, se n é primo ele não possui divisor não trivial menor ou igual do que \sqrt{n}. Então basta buscar candidatos a divisores de 2 até [\sqrt{n}], onde [\sqrt{n}] é o maior inteiro positivo menor ou igual do que \sqrt {n}. Podemos simplificar mais ainda testando o dois e em seguida somente os ímpares da nossa lista restrita. A seguir vamos exibir um código em C que determina se o número é primo ou composto adaptado de um código disponibilizado pelo IME.
Algoritmo
________________________________________________________
#include <stdio.h>
int main()
{
int num,divisor,ehprimo,cont,resultado, resto;
printf("Por favor digite um numero inteiro==>");
scanf("%d",&num);
if((num<=1)||(num!=2 && num%2==0))
{
ehprimo=0;
printf ("\n seu número ou é par e distinto de 2 ou é menor que 2.");
}
else
{
ehprimo=1;
}
divisor=1;
cont=0;
resultado=num;
while((ehprimo==1)&&(divisor<=resultado)&&(num!=2))
{
divisor=divisor+2;
resultado=num/divisor;
resto=num%divisor;
printf("\n candidato a divisor %d, parte inteiro %d",divisor,resultado);
printf(", resto %d ",resto);
cont ++;
if(num%divisor==0)
{
ehprimo=0;
}
else
{
ehprimo=1;
}
}
if((num%2!=0)&&(num>1))
{
printf ("\n foram realizadas %d divisões",cont);
}
if(ehprimo==1)
{
printf("\n %d eh primo", num);
}
else
{
printf("\nO %d nao eh primo.",num);
}
return 0;
}
________________________________________________________
O código funciona, porém, tem custo computacional O(\sqrt{n}).
Desafio
2) (OIbM 2014) Dado um conjunto X e uma função f:X \to X denotamos, para cada x \in X, f^1(x)=f(x) e, para cada j \geq 1, f^{f(j+1)}(x)=f(f^j(x)). Dizemos que a \in X é um ponto fixo de f se f(a)=a. Para cada número real x, definimos \pi(x) como o número de primos positivos menores ou iguais a x. Dado um número positivo n, dizemos que f:\{1,2,3,...,n\} \to \{1,2,3,...,n\} é catracha se f^{f(k)}(k)=k para todo k\in\{1,2,3,...,n\}. Prove que:
a) Se f é catracha, então f tem pelo menos \pi(n)-\pi(\sqrt{n})+1 pontos fixos.
b) Se n\geq 36, então existe uma função catracha com exatamente \pi(n)-\pi(\sqrt{n})+1 pontos fixos.
Referências
MAC-110 - Numero Primo - Três solucoes para o mesmo problema. Disponível em: ime.usp.br/~yw/2012/mac110/material/primo.html.
MARTINEZ, F. B. et al. Teoria dos Números: um passeio com primos e outros números. IMPA, Rio de Janeiro, 5ª edição, 2018.
Provas e gabaritos. Disponível em: OBM - Olimpíada Brasileira de Matemática.
Nenhum comentário:
Postar um comentário