Scientia.ro - stiri stiinta si tehnologie

sci_fan

Intrebare rezolvata

Cum functionează ciurul lui Sundaram ?

...un alt algoritm de tip ciurul lui Eratostene, cu care se determina toate numerele prime mai mici decat un intreg dat...

Cel mai bun raspuns - Ales de cel care a pus intrebarea

• 
  Scientia.QA

  de fapt, algoritmul generează o listă de numere prime de valoare maxim egală cu 2n+1, plecând de la lista numerelor de la 1 la n, n-număr natural.

  Iată cum:

  - se pleacă cu lista numerelor naturale de la 1 la n;

  - se elimină din listă toate numerele de forma i+j+2ij pentru care:

  • i şi j sunt numere naturale, cu 1≤i≤j şi
  • i+j+2ij≤n.

  Fiecare din numerele care rămâne din lista de numere iniţială se dublează şi se incrementează cu 1. Rezultă astfel o listă de numere prime - toate numerele prime mai mici sau egale cu 2n+1, cu excepţia lui 2, care trebuie adăugat la începutul şirului rezultat.

   

  Iată un exemplu, pentru n=11  (1,2,3,4,5,6,7,8,9,10,11)

  i=1 j=1 --> se elimina i+j+2ij=4

  i=1 j=2 --> se elimina i+j+2ij=7

  i=1 j=3 --> se elimina i+j+2ij=10

  Orice alta pereche (i,j) încalcă regula i+j+2ij≤n=11.

  Aşadar şirul iniţia la fost redus la (1,2,3,5,6,8,9,11).

  Se dublează fiecare număr şi se adaugă 1:

  Se obţine: (3,5,7,11,13,17,19,23).

  Se adaugă la început 2 şi rezultă (2,3,5,7,11,13,17,19,23).

  
  

  • 2010-10-11 23:24
  • 1
  • 0
  •