Descobrir se um número é primo!

DMS_
(usa elementary OS)

Enviado em 06/12/2012 - 11:14h

Bom Dia!

Estamos realizando alguns exercícios, e dentre estes tem um curioso e que eu acho muito legal, o famoso algoritmo para descobrir se um número é primo.
Número primo é aquele número que só é divisivel por 1 e ele mesmo, ou seja, tem resto de divisão 0! Como a matéria é de VBA (eca!) fizemos este em VBA, realizei os testes com os 1000 primeiros números primos, e ele acertou todos.
Agora, a lógica que eu usei que estou com dúvida.
Bom, sabemos que um número é primo quando apenas 1 e ele mesmo tem resto da divisão por 0.

i = 2 //i já começa com 2 pois já sabemos que resto de divisão por 1 é zero

verifica = False

Do

  if n Mod i = 0 And n <> i Then  //verifica se o resto da divisão de n por i é zero, verifica do numero 2 até n-1

    verifica = True               //Caso seja True, ele já não é primo, além de 1 e ele mesmo, ele possui mais um número que é divisivel

  End If

  i = i + 1

Loop While i < n And verifica = False //faz o loop enquanto i for menor que n e verifica ser false

 

Está em VBA que é um coco, vou tentar fazer em C depois, então o que ele basicamente faz é verificar se o resto da divisão de n e i é zero, se sim ele já não é numero primo, pois numero primo só possui resto zero por 1 e ele mesmo, e ele faz essa verificação de 2 até n-1.
Queria saber se tem como otimizar, pel oque andei lendo, posso fazer até n/2 pois o maior divisor de um número, além dele mesmo, é a metade desse número.

Sei que está uma caca isso, mas foi o que consegui fazer :/
Vlw.

DMS_
(usa elementary OS)

Enviado em 06/12/2012 - 15:07h

up