[Contest] Numeri primi tramite Crivello di Erastotene

« Older   Newer »
  Share  
CAT_IMG Posted on 5/2/2013, 22:33     +1   -1

So implementare gli object

Group:
Admin
Posts:
1,215
Reputazione:
+150

Status:


Ciao a tutti.

Tempo fa, avevo letto un ottimo articolo sull'implementazione del Crivello di Erastotene in Python per ricavare tutti i numeri primi da 2 a n.
L'algoritmo usava strutture di tipo LIFO (pop e push, per intenderci) e quindi il codice era molto veloce.
Io NON vi chiedo di fare questo in AutoIt ( :asd: ).

Dovete semplicemente e con il metodo che preferite implementare un algoritmo che trovi i numeri primi da 2 a n, che usi il Crivello di Erastotene.

Non fatevi prendere dalla pigrizia e partecipate tutti, cogliamo l'occasione per ridare un po' di vita al forum!

Linguaggi: AutoIt, C/++/#, Python, Lua, PHP
Scadenza: 17/02/2013

Edited by ‡ (dd) - 15/2/2013, 15:35
 
Top
doublechar
CAT_IMG Posted on 5/2/2013, 23:12     +1   -1




CODICE
#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[])
{
       int n = 30;
       cout << "Mostra i numeri primi da 2 fino a ...";
       cin >> n;
       cout << endl;

       int *setaccio = (int*) malloc(sizeof(int) * (n - 2));
       int *numeriPrimi = (int*) malloc(sizeof(int) * (n - 2));

       for (int i = 2; i <= n; i++)
       {
               *(setaccio + (i-2)) = i;
       }

       int indexDivisore = 0;
       while (1)
       {
               int divisore = *(setaccio+(indexDivisore++));
               if (divisore*divisore > n) break;

               int indexnumeriPrimi = 0;
               for (int i = 0; i < n-1; i++)
               {
                       if (*(setaccio+i) % divisore == 0)
                       {
                               continue;
                       }
                       *(numeriPrimi+(indexnumeriPrimi++)) = *(setaccio+i);
               }

               memcpy(setaccio, numeriPrimi, sizeof(int) * (n-2));
               memset(numeriPrimi, 0, sizeof(int) * (n-2));
       }

       for (int i = 0; *(setaccio+i) >= 0; i++)
       {
               cout << *(setaccio+i) << endl;
       }
       
       getchar(); // \n del cin
       getchar();

       return 0;
}


ti odio dd, davvero
 
Top
CAT_IMG Posted on 5/2/2013, 23:16     +1   -1

So implementare gli object

Group:
Admin
Posts:
1,215
Reputazione:
+150

Status:


CITAZIONE (doublechar @ 5/2/2013, 23:12) 
CODICE
#include <iostream>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[])
{
       int n = 30;
       cout << "Mostra i numeri primi da 2 fino a ...";
       cin >> n;
       cout << endl;

       int *setaccio = (int*) malloc(sizeof(int) * (n - 2));
       int *numeriPrimi = (int*) malloc(sizeof(int) * (n - 2));

       for (int i = 2; i <= n; i++)
       {
               *(setaccio + (i-2)) = i;
       }

       int indexDivisore = 0;
       while (1)
       {
               int divisore = *(setaccio+(indexDivisore++));
               if (divisore*divisore > n) break;

               int indexnumeriPrimi = 0;
               for (int i = 0; i < n-1; i++)
               {
                       if (*(setaccio+i) % divisore == 0)
                       {
                               continue;
                       }
                       *(numeriPrimi+(indexnumeriPrimi++)) = *(setaccio+i);
               }

               memcpy(setaccio, numeriPrimi, sizeof(int) * (n-2));
               memset(numeriPrimi, 0, sizeof(int) * (n-2));
       }

       for (int i = 0; *(setaccio+i) >= 0; i++)
       {
               cout << *(setaccio+i) << endl;
       }
       
       getchar(); // n del cin
       getchar();

       return 0;
}


ti odio dd, davvero

Avevo detto i numeri primi :asd:
 
Top
doublechar
CAT_IMG Posted on 5/2/2013, 23:17     +1   -1




Tu vuoi che lo finivo entro le 11 e 11, ecco cosa ho fatto, ora lo aggiusto meglio, ti odio
 
Top
CAT_IMG Posted on 5/2/2013, 23:19     +1   -1

So implementare gli object

Group:
Admin
Posts:
1,215
Reputazione:
+150

Status:


CITAZIONE (doublechar @ 5/2/2013, 23:17) 
Tu vuoi che lo finivo entro le 11 e 11, ecco cosa ho fatto, ora lo aggiusto meglio, ti odio

La scadenza iniziale era 22:50 a dirla tutta, e quando te l'ho detto mi hai risposto
CITAZIONE
Ok

con aria nabbosamente spavalda :asd:
 
Top
doublechar
CAT_IMG Posted on 5/2/2013, 23:21     +1   -1




Ma ora non sto bene per programmare e volevo provarci, perchè se ti dicevo che non mi bastava perdevo tempo XD
 
Top
Muro1
CAT_IMG Posted on 11/2/2013, 13:18     +1   -1




CODICE
;badpr0g

Global $n = 30, $setaccio[$n], $v = 0, $del

For $i = 2 To $n
 
  $setaccio[$i - 2] = $i
 
Next

Do
 
  del_multiple()
 
Until ($del * $del) > $n

For $i = 0 To $n - 2
 
  If $setaccio[$i] <> 0 Then ConsoleWrite($setaccio[$i] & @TAB)
         
Next          

Func del_multiple()

  For $i = (0 + $v) To $n - 2

         $del = $setaccio[$v]

         If $setaccio[$i] <> $del And IsInt($setaccio[$i] / $del) Then
               
                $setaccio[$i] = 0
               
         EndIf
         
  Next
 
  $v += 1
 
EndFunc


La mia implementazione in autoit.
 
Top
6 replies since 5/2/2013, 22:33   95 views
  Share