• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Knuxus

[VB.NET ]Ajuda com Crivo de Eratosthenes

13 mensagens neste tópico

Boas, estou a tentar incluir vários algoritmos de encontrar primos, e tenho dificuldades em perceber este, ou pelo menos traduzir para código, se alguém poder ajudar com o Crivo de Eratóstenes.

no wikipedia tenho bastante pseudocodigo mas parece me um pouco diferente desta maneira...

Criar um array com todos elementos inicializados a 1, as células de cujo índice seja numero  primo permanecerão a 1. todas as outras células ficarão a zero.

iniciando na célula 2( o índice 1 e 2 são primos), toda a vez que uma célula for encontrada com valor 1, há que percorrer o resto do array e por a zero toda a célula cujo índice e um múltiplo do índice da célula inicial que e 1.

por exemplo para o índice 2 todos os elementos para alem do 2 que são múltiplos de dois passarão a conter zero(índices 4,6,8,10, etc...) para o índice 3 para alem do 3, os que são múltiplos passarão a conter zero (6,9,12,15,etc...)

Espero que consigam esclarecer me isto em código... não consigo avançar sem isto.

Obrigado.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Ok... alguem pode ajudar a traduzir isto para codigo?

// arbitrary search limit

limit ← 1.000.000                 

// assume all numbers are prime at first

is_prime(i) ← true, i ∈ [2, limit]

for n in [2, √limit]:

    if is_prime(n):

        // eliminate multiples of each prime,

        // starting with its square

        is_prime(i) ← false, i ∈ {n², n²+n, n²+2n, ..., limit}

for n in [2, limit]:

    if is_prime(n): print n

isto e de http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

em C devia ficar mais ou menos isto:

#define LIMIT 1000000

int eratosthenes()
{
  char vals[LIMIT]
  int i,j;

  for(i=2;i<LIMIT;i++)
    vals[i]=1;

  for(i=2;i<sqrt(LIMIT);i++)
    if(vals[i])
      for(j=i*i;j<LIMIT;j+=i)
        vals[j]=0;

  return 0;
}

não deve ser complicado passar para VB  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

em C devia ficar mais ou menos isto:

#define DIM 1000000

int eratosthenes()
{
  char vals[DIM]
  int i,j;

  for(i=2;i<DIM;i++)
    vals[i]=1;

  for(i=2;i<sqrt(DIM);i++)
    if(vals[i])
      for(j=i*i;j<DIM;j+=i)
        vals[j]=0;

  return 0;
}

não deve ser complicado passar para VB  :P

Obrigado, nao e complicado so que tenho e problema com a condicao criada pelo if, nao sei nada do C(ainda) por isso nao percebo muito bem como funcioan esse if... nao sei com o que esta relacionado... provavelmente com o for, mas se alguem poder explicar...

O do java acho que percebi,mas nao vi bem o algoritmo a ser usado pois isso parece a maneira convencional de fazer a verificacao dos primos... nao a do crivo...

obrgiado...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Esta funcao em vb.net verifica se determinado inteiro é primo

    Public Function IsPrime(ByVal TestPrime As Int32) As Boolean
        Dim TestNum As Int32
        Dim TestLimit As Int32

        '   Eliminate even numbers
        If TestPrime Mod 2 = 0 Then Exit Function

        '   Loop through ODD numbers starting with 3
        TestNum = 3
        TestLimit = TestPrime
        Do While TestLimit > TestNum

            If TestPrime Mod TestNum = 0 Then
                '   Uncomment this if you really want to know
                ' MsgBox("Divisible by " & TestNum)
                Exit Function
            End If

            '   There's logic to this.  Think about it.
            TestLimit = TestPrime \ TestNum

            '   Remember, we only bother to check odd numbers
            TestNum = TestNum + 2
        Loop

        '   If we made it through the loop, the number is a prime.
        IsPrime = True
    End Function

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Isto e a maneira convencional, pois com esta nao tenho problemas, o crivo e que esta em questao...

Obrigado..

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

em C, 0 é equivalente a falso e 1 (ou qualquer outro inteiro) é equivalente a verdadeiro.

if(vals[ i ]), testa se vals[ i ] é verdadeiro, isto é, se vals[ i ] é diferente de 0.

repara que em vez de inicializar o array com o valor True, inicializei com o valor 1.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A funcão IsPrime que eu postado anteriormente estava a excluir o 2 como não sendo primo.

Este exemplo calcula os primeiros 50 digito de 1 a 50.

    Public Function IsPrime(ByVal TestPrime As Int32) As Boolean
        Dim TestNum As Int32
        Dim TestLimit As Int32

        '   Eliminate even numbers
        If TestPrime = 2 Then IsPrime = True


        If TestPrime Mod 2 = 0 Then Exit Function

        '   Loop through ODD numbers starting with 3
        TestNum = 3
        TestLimit = TestPrime
        Do While TestLimit > TestNum

            If TestPrime Mod TestNum = 0 Then
                '   Uncomment this if you really want to know
                'MsgBox("Divisible by " & TestNum)
                Exit Function
            End If

            '   There's logic to this.  Think about it.
            TestLimit = TestPrime \ TestNum

            '   Remember, we only bother to check odd numbers
            TestNum = TestNum + 2
        Loop

        '   If we made it through the loop, the number is a prime.
        IsPrime = True
    End Function


        Dim lista(49) As Int32

        For I As Int32 = 0 To 49
            If IsPrime(I) Then
                lista(I) = 1
            Else
                lista(I) = 0
            End If

        Next
        For i As Int32 = 0 To 49
            If lista(i) = 1 Then Console.WriteLine(i.ToString)
        Next

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Asgorath, eu nao estou a dizer que a tua maneira esta errada, so que a tua maneira de encontrar primos nao e a que o Eratosthenes usa, eu ja tenho o codigo dessa maneira, so que precisava mesmo do crivo que e o que referi, que  e explicado aqui http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes , se conseguires entender isto e traduzir em codigo, ajudava imenso...

Obrigado pela ajuda.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Outra duvida de C...

For i = 2 To 1000
                numeros(i) = 1
            Next

            For i = 2 To Math.Sqrt(1000)
                If numeros(i) Then
                    For j = i * i To 1000
                        j += 1
                        numeros(j) = 0
                    Next
                End If
            Next

eu duvido que aquele j+= 1 devia ficar aqui, mas tambem nao sei bem a maneira como se possa encaixar para funcionar tao bem como funciona no c...

ou entao devia meter o j=i*i antes talvez para declarar o j como tal variavel... vou continuar a experimentar

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

atenção que não é j+=1 mas sim j+=i.

tens que definir o incremento da variável j como sendo i unidades. não percebo nada de VB, mas se calhar tens que usar um while para fazer isso.

a versão com while fica assim:

j=i*i

while j<1000

  numeros(j)=0

  j=j+i

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Nem sei como agradecer,funciona bem... se alguem precisar do codigo...e so perguntar  :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora