Generare de numere prime

[•rEbyTer]

Cum pot genera numere prime cu un algoritm efectiv. (chiar şi cu optimizări pe biţi)

[•wefgef]

Nu stiu cum poti genera numere prime decat cu un algoritm neefectiv .

[•rEbyTer]

da , lol .... daca as face o problema la nationala cu un algoritm de generare a numerelor prime neefectiv as lua credca sub 30puncte.. :/

[•pauldb]

Ai aici un articol.

[•wefgef]

Aici ai mai multe despre cuvantul efectiv: http://youtube.com/watch?v=bzZMMQYj6E4

[•rEbyTer]

Cod:

 
  //class PrimeNumbersSieve5 
  final int MAXSIZE = 100000000/2/8+1;
  char[] p = new char[MAXSIZE];

  //(p[i>>3]&(1<<(i&7))) == 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 >> 3] & (1 << (i & 7))) == 0) {
        for (j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= n; j += (i << 1) + 1) {
          p[j >> 3] |= (1 << (j & 7));
        }
      }
    }
    for (i = 1; 2 * i + 1 <= n; ++i)  
         if ((p[i >> 3] & (1 << (i & 7))) == 0) 
             nr++;
    return nr;
  }

Sursa originală aici.

Cum scriu toate numerele prime (generate) intr-un fişier?(sau măcar să le afişez, nu ştiu dacă pot scrie folosind Java in fişiere...)
Faza cu operaţii pe biţi este un pic mai "ciudată" pentru mine. Voi începe să citesc mâine despre combinatorică, şi pe acolo am nevoie de operaţii pe biţi. Poate aşa o să înţeleg mai bine.

P.S.:Este prea efectiv sa mai folosesc cuvantul "efectiv" . Vroiam să spun eficient . Dar doar vroiam .

L.E.: Aparent nu văd cine ştie ce diferenţă între sursa din Java şi sursa din C/C++. M-a aburit chestia cu i+=1; (înloc de ++i sau i++, dar e Java, nu?)
Ce fişiere header-e am nevoie pentru a compila sub C/C++ ?

Deja văd şi nişte clase în funcţie (dacă or exista) şi am ajuns aburit complet. Sunt a 9ua. doh.

[•sima_cotizo]

Din cate vezi si in sursa zice :

Cod:

  //(p[i>>3]&(1<<(i&7))) == 0 if 2*i + 1 is prime

Deci, toate numerele prime din vector indeplinesc conditia aia (mai putin 2, care e singurul numar par si prim, care e luat separat). In ultimul for se numara toate numerele prime. Ca sa le afisezi poti adauga un printf("%d\n", i*2+1); alaturi de nr++; . Bineinteles, pe 2 il afisezi separat


Legat de "diferentele" Java/C++, cred ca nu reprezinta un impediment pentru cei care lucreaza in C : i+=1 exista si in C++, a fost pus acolo pentru mai multa claritate, daca te uiti mai sus o sa vezi si i+=2. Si pentru a compila functia asa cum e ea, cred ca nu ai nevoie de niciun header. Daca mai bagi si afisare, incluzi si cstdio sau stdio.h sau ce crezi ca mai ai nevoie... Si faptul ca functia este "public" tine de Java, in C++ scrii fara "public" (daca nu o bagi in vreo clasa)

[•rEbyTer]

Este mirific. In 956ms am generat primele 148933 numere prime (exclusiv 2). Cu un asemenea algoritm pot efectua operatii inimaginabile.

Funcţionează! Vă mulţumesc la toţi cei care m-aţi ajutat.

ca să pot compila funcţia am făcut câteva modificări (Google îmi e prieten):

Cod:

#define MAXSIZE  100000000/2/8+1 
char *p = new char[MAXSIZE];

înloc de:

Cod:

final int MAXSIZE = 100000000/2/8+1;
char[] p = new char[MAXSIZE];

Mai am o întrebare. Ce reprezintă numărul 100000000/2/8+1 ?

L.E.: Am calculat 2^10.000 .. Rezultatul are 3011 cifre ..... este fantastic
L.E.2: Daca la naţională tree să descompun mai multe numere în factori primi e OK algoritmul ăsta. Este atât de eficient.. mi se pare incredibil ... Nici nu se compară cu clasicul brute-force. Ăsta cred că merge şi la internaţională....

Aşa, de curiozitate, cine s-a gândit la asemenea optimizări? Să ştiu şi eu cine a muncit atâta timp să dea naştere la asemenea algoritmi .

[•wefgef]

Pentru a calcula toate numerele prime mai mici decat un numar MAXN am putea sa folosim un vector de char de lungime MAXN. Observam ca singurul numar prim par este 2, deci putem reduce memoria la MAXN/2. Deoarece lucram pe biti, putem sa stocam intr-un singur char (care are 8 biti) informatia necesara pentru 8 numere. De aici rezulta ca avem nevoie de un vector de marime MAXN/2/8 (Se mai pune +1 pentru siguranta).

[•rEbyTer]

10x