Imprimă pagina - Ciurul lui Eratostene

Titlul: Ciurul lui Eratostene
Scris de: MciprianM din Ianuarie 30, 2008, 19:34:28

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)

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Mircea Dima din Ianuarie 30, 2008, 19:57:24

La prima intrebare:

((i*i)<<2) inseamna 4i^2 ... (a<<b) inseamna a*(2^b)

Later Edit: (Never mind explicatia de mai sus :P) 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.

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: MciprianM din Ianuarie 31, 2008, 14:21:35

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

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Andrei Grigorean din Ianuarie 31, 2008, 14:32:13

Citat din mesajul lui: marginean ciprian din Ianuarie 30, 2008, 19:34:28

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.

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: MciprianM din Ianuarie 31, 2008, 15:08:30

sunt suficiente
poti sa-mi9 zici in logn

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Andrei Grigorean din Ianuarie 31, 2008, 15:29:30

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 ].

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: MciprianM din Februarie 01, 2008, 13:22:30

Cod:

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

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

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Andrei Grigorean din Februarie 01, 2008, 21:19:45

Da, asa e :).

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Glodeanu Ioan Daniel din Februarie 26, 2008, 18:31:17

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!

Titlul: Răspuns: Ciurul lui Eratostene
Scris de: Stefan Istrate din Februarie 20, 2009, 02:09:13

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Articole => Subiect creat de: MciprianM din Ianuarie 30, 2008, 19:34:28