Ciurul lui Eratostene

[•MciprianM]

Vreau sa intreb daca nu ar fi mai corect ca in a patra si a cincea bucata de cod, conditia de oprire a primului for sa fie ((i*i)<<2)+(i<<2)+1<=n in loc de ((i*i)<<1)+(i<<1)<=n? De la (2*i+1)².
Asta de mai jos ar fi bucata a 4 din articol:

Cod:

//class PrimeNumbersSieve4   
final int MAXSIZE = 1000000/2+1;   
char[] p = new char[MAXSIZE];   
 
//p[i] == 0 if 2*i + 1 is prime   
 
public int getTheNumber(int n) {   
  int i, j, nr = 1;   
  for (i = 1; ((i * i) << 1) + (i << 1) <= n; i += 1) {   
    if (p[i] == 0) {   
      for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1) {   
        p[j] = 1;   
      }   
    }   
  }   
  for (i=1; 2 * i + 1 <= n; ++i)   
      if (p[i] == 0) nr++;   
  return nr;   
} 

P.S. Problema(Patcas Csaba) : Sa se numere toti bitii egali cu 1 din reprezentarea binara a numerelor de la 1 la n? O(n)

[•blasterz]

La prima intrebare:
 
((i*i)<<2) inseamna 4i^2     ... (a<<b) inseamna a*(2^b)

Later Edit: (Never mind explicatia de mai sus ) da cred ca e bine cum zici ... ecorect in ambele feluri... e mai optim cum zici tu

La pb cu numarul de biti egali cu 1 din reprezentarea binara a numerelor de la 1 la n in O(n):
1) precalculez a[ i ] ( i=1, 2^16) a[ i ]=nr de bitii al numarului i. Asta se poate face in O(T log T)
   sau  in O(T) (T=2^16) cu memoizare ( ceva in genul codului gray ... din i ma duc in j unde j are un bit de 1 mai putin decat i)

2) pentru i=1 la n
         sol+=a[i %(1<<16)] + a[i>>16]; // O(n)

Sau poti aplica memoizarea pt intregul sir dar s-ar putea sa fie mai lent datorita recursivitatii.

[•MciprianM]

!.credeam ca am gresit ceva
2. Cam complicata rezolvarea ta... daca n e un milion si timp 0.1 sec..

[•wefgef]

P.S. Problema(Patcas Csaba) : Sa se numere toti bitii egali cu 1 din reprezentarea binara a numerelor de la 1 la n? O(n)

Relatiile astea ar trebui sa fie suficiente:

Cod:

v[0] = 0;
v[i*2] = v[i];
v[i*2+1] = v[i]+1;

Problema poate fi rezolvata si in O(log N). Probabil ca se poate si mai bine, insa o rezolvare de complexitate mai buna nu imi vine acum in minte.

[•MciprianM]

sunt suficiente
poti sa-mi9 zici in logn

[•wefgef]

Scrii numarul N in baza 2. Vei obtine o configuratie de M (M = log N) biti. De exemplu pentru N = 25, vei obtine M = 5, iar configuratia va arata asa:

Cod:

Bit[4] = 1;
Bit[3] = 1;
Bit[2] = 0;
Bit[1] = 0;
Bit[0] = 1;

Vrei sa vezi pentru fiecare pozitie i (0 <= i < M) de cate ori va aparea 1 in scrierea tuturor numerelor de la 1 la N.
Notam cu Left[ i ] numarul format de Bit[M-1], Bit[M-2], ... , Bit[i+1], iar cu Right[ i ] numarul format de Bit[i-1], Bit[i-2], ... , Bit[0]. In exemplul de mai sus, pentru i = 2, Left[2] = 3, iar Right[2] = 1. Numarul de aparitii ale lui 1 pe pozitia i in scrierea tutror numerelor de la 1 la N este:

Cod:

R[i] = Left[i] * 2^i + (Bit[i] ? (Right[i]+1) : 0).

Raspunsul cautat este suma de R[ i ].

[•MciprianM]

Cod:

//Left[i] in loc de left[i]-1;

se adauga la ce ai zis tu cazul cu 000...0. 

[•wefgef]

Da, asa e .

[•DanielG]

Cod:

public static void main(String[] arg) {   
  double tick = System.currentTimeMillis();   
  for (int i = 0; i < 10; ++i) {   
    System.out.println("Run " + i   
  + " result: "+   
    new PrimeNumbersSieve1().   
    getTheNumber(1000000));   
  }   
  System.out.println(" 10 runs of " 
+ "PrimeNumbersSieve1()."   
+ "getTheNumber(1000000) "   
+ "lasted: "   
+ (System.currentTimeMillis()   
- tick)   
* 1e-3 + " seconds");   
} 

Poate cineva sa scrie acest algoritm in Pascal sau pseudocod? Multumesc!

[•stef2n]

Discutiile pot continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3682.0