Algoritm de verificare a numerelor prime super optimizat.

Al tau are complexitatea O(sqrt(n)), cel pe care ti-l propunem are complexitatea O( log₂n ), cred ca asta zice tot. Cat despre ce ai zis tu, tu tot nu intelegi cum functioneaza ciurul lui Eratostene. Ciurul este pentru a determina care numere sunt prime si care nu sunt dintr-un anumit interval ( corect  este multime ), in cazul tau [ 1, 49 ]. Dupa construirea, poti verifica asta in O(1), deoarece tu reti intr-un vector, sa zic isPrime, daca elementul i este prim sau nu, nu al-i lea element prim !

Edited by secretalex92, 19 October 2010 - 21:26.

Asa se intampla cand nu exprimi ce vrei de la inceput.
Pentru ce vrei tu e de ajuns sa ai un vector de 50 elemente unde pe pozitia i ai valoarea true/false.Si atunci iti ramane sa verifici daca pe pozitia sir[nr_meu] ai true/false (prim sau nu) fara sa parcurgi vectorul de fiecare data sau altceva.

O alta observatie,daca scopul programului tau este sa genereze toate combinatile loto 6/49 avand doar numere prime,atunci faci combinatii de 6 din 15  (2 3 5 7 11 13 17 19 23 29 31 37 41 43 47) si nici nu mai trebuie sa verifici daca sunt prime sau nu.

Nu am inteles o chestie aici si, daca se poate, v-as ruga sa mi-o clarificati:

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

Spune asa:
p[i]=0 daca numarul este prim.
Acuma:
p[2] nu este 0 ??? p de oricare i este 0 ptr ca nu este initializat vectorul, avem doar p[1000001] si atat.
deci tot timpul acel if se va executa ptr ca tot timpul p[i] va fi 0.
Nu e asa ? Va rog sa ma lamuritit si pe mine.

Multumesc !

PS: Algoritmul este din linkul acele de pe infoarena.

In java variabilele sunt initializate automat daca nu le-ai initializat explicit. (un alt plus al limbajelor de nivel inalt)

Ia pas cu pas fiecare instructiune!

p[2] == 0 e prim , acum merge pe p[4] p[6] p[8] .. etc si le seteaza pe 1.
p[3] == 0 e prim merge p[6] p[9] p[12] seteaza pe 1.
.....
ajunge pe p[4] care este 1 pentru ca a fost setat la pasii anterior, deci nu se executa if-ul. Si asa mai departe.

Edited by doriaal, 20 October 2010 - 14:45.

Revin cu intrebari:

Am citit despre operatii cu biti atat cat am gasit si tot am o intrebare care cred eu ca are o impornatanta capitala si fara ea nu as putea folosi deloc operatiile pe biti in nici un fel.

Dau un scenariu (dintr-un tutorial):

Quote

Sa presupunem ca as fi eu in locul acelui programator.
Sa zicem ca vreau sa transform toate numerele, cu ajutorul unui for, in cu totul alte numere. Sa zicem ca acel for s-ar face prin mutarea cu doua pozitii a ultimilor 3 biti de la fiecare numar. De unde post sa stiu eu chestia asta ? De unde as putea sti ca prin mutarea cu nu stiu cate postii la stanga sau la dreapta numerle se transforma in cutare numere ? Este vreun algoritm ceva de asezare a bitilor sau cum pot sti ca prin numai mutarea a bitilor cu nu stiu cate pozitii intr-un sens sau in altul ei se pot transforma in numerele dorite ? De unde post sti in ce anume si CUM anume se pot transforma numerele in binar ca sa pot apela la acest lucru cand am nevoie ?

Un alt exemplu mai clar:

Quote

Intrebari: De unde ar putea sti programatorul dinainte in ce s-ar transforma numerele respective ca sa poate folosi acest lucru in algoritmul sau ?
De unde poate sti ca toate se vor comporta la fel ??? Poate unu se transforma in multiplu de 3 dar poate unele nu se supun regulii si se vor transforma in altceva.


Multumesc mult !

Edited by Krisler12, 20 October 2010 - 19:38.

Nim'nea ?
Chiar as vrea sa stapanesc chestiile astea...

Multumesc !

Nu-ti raspunde nimeni pentru ca intrebarile sunt aiurite. E ca si cum ai intreba daca inmultesc cu doi un numar intreg rezultatul este par sau impar ?
Asa cum sti ca un numar este par daca se divide cu 2, sau ca o inmultire cu 10 a unui numar inseamna adaugarea unui zero la sfarsit/mutarea virgulei cu o pozitie.Asa si in sistemul in binar.

De exemplu ca sa verifici daca un numar este par/impar este de ajuns sa verifici daca ultimul bit (LSB) este 0 (cu ajutorul operatiei & 1,fiind mult mai rapid ca %2).
Numerele de forma 2^n,in binar sunt reprezentate prin 1 urmat de n zerouri. (2^3 = 1000, 2^10=10000000000)
Lucrurile astea se invata prin lucrul efectiv cu ele, cauta tutoriale in engleza (Bitwise operations / Bitwise tricks) .

Edited by doriaal, 21 October 2010 - 16:23.

E asa greu de inteles ca un calculator lucreaza doar cu valori de 0 si 1? Orice altceva, incepand de la cel mai marunt byte si terminand cu faptul ca te poti exprima pe acest forum folosind un browser, e doar o reprezentare la un nivel mai superior. Tu crezi ca lucrezi cu valori in baza 10? Teapa, de fapt pentru un PC sunt doar siruri de 0 si 1. Pune mana pe o carte sau doua ca sa intelegi chestia asta inainte ca sa pui intrebari prostesti de genul de unde stie un programator ce face shiftarea cu o pozitie la stanga. Iti zic eu de unde: din clasa a IV-a de cand a invatat transformarea dintr-o baza de numeratie in alta.

Edited by NumeDeCod, 21 October 2010 - 20:01.

 doriaal, on 21st October 2010, 17:14, said:

1. Dar de unde stii ca numerele impare au 0 la sfarsit si cele pare nu ? Este vreo regula de formare a lor sau trebuie sa le verifici tu manual pe fiecare in parte (pana la maximul care te intereseaza pe tine ca doar nu pana la infinit ) si sa observi care e diferenta intre cele pare si cele impare si apoi sa deduci o regula si apoi un algoritm ?

2. Daca scriu algoritmul asa cum il stim cu totii, clasic, adica cu N%2 etc. si apoi il iau in compilator si ii fac debug si apoi fur codul scris in asm iar in final iau acest cod in asm si rescriu programul de forma

functie prim int n, int k)
_asm{
		  ;codul in asm obtinut care nu este altceva decat dezasamblarea codulul initial in c++
		 }

Care este mai rapid in acest caz:
aceeasi functie scrisa folosind operatiile pe biti sau asta de care zic eu in asm ?

Multumesc !

 Krisler12, on 21st October 2010, 21:03, said:

1) Citeste o data despre forma/repezentarea binara a numerelor !

0   0 0 0
1   0 0 1
2   0 1 0
3   0 1 1
4   1 0 0
...

2) Nu e mai rapid daca faci copy & paste de la compilator. E mai rapid cand scrii tu cod optim.

Edited by neagu_laurentiu, 21 October 2010 - 20:24.

Numerele pare au 0,iar cele impare 1, n-am fost foarte precis mai sus.
In rest tot n-ai inteles ideea, citeste si ce a zis NumeDecod.

Ca si chestie, compilatoarele moderne pot genera cod destul de optimizat iar unele asa zise optimizari(incercate de incepatori) cu operatii pe biti pot sa nu faca extraordinare diferente.
Inca n-are rost sa iti bati  capu cu operatii pe biti sau limbaj de asamblare, stapaneste mai intai limbajul C/C++ si algoritmii fundamentali.

Edited by doriaal, 21 October 2010 - 20:27.

Is it just me, sau "super" din titlul thread-ului chiar e amuzant?

 OriginalCopy, on 21st October 2010, 21:46, said:

Hai mai, nu fi rau, omul chiar e dedicat in ceea ce face, cred ca e un an doar de cand il stiu eu ca lucreaza la programul care iti da numerele castigatoare la loto

Într-adevăr +1 karma pentru entuziasm. Nu sunt ironic, e pe bune

E destul de simplu. Conversia dintr-o baza in alta mi se pare ca se invata in clasa a 5a. Practic un numar (cum in vedem noi in baza 10) poate fi reprezentat in orice baza. Baza 2 are doar doua cifre (0 si 1) baza 8 are opt cifre (de la 0 la 7) baza 16 are cifre de la 0 la 9 si de la a la f, samd. Asa cum in baza zece numeri 0,1,2,3, ..., 9, 10, 11, ... in baza 2 vei avea 0,1,10,11,100,101,etc. Ceea ce inseamna ca numarului 2 in baza 10 ii corespunde numarul 10 in baza 2, numarului 3 ii corespunde 11, lui 4 ii corespunde 100, s.a.m.d
Ca sa faci aduci un numar din baza 2 in baza 10, trebuie sa tii cont ca fiecarei cifre din numar ii corespunde o putere a lui 2. Cifra cea mai putin semnificativa are corespondent 2^0 (2 la puterea 0), urmatiarea 2^1, etc. De exemplu avem in binar:
1110101
6543210 -> puterile lui 2.
numarul in baza 10 este : 1 * 2^0 + 0 * 2^1 + 1 * 2^2 + 0* 2^3 + 1* 2^4 + 1 * 2^5 + 1 * 2^6 = 1+ 4 + 16 + 32 + 64 = 117.
Conversia inversa (din baza 10 in baza 2) este asemanatoare.

Algoritm 'super optimizat' care verifica in timp constant daca un nr este prim sau nu:

bool isPrime(int p)
{
	if (p >= 2) {
		if ((p == 2) || (p == 3) || ((((p%24)*(p%24) - 1) % 24) == 0)) {
			return true;
		}
	}
	return false;
}

Meritul nu este in totalitate al meu... ideea mi-a venit de aici http://www.codeproje...L-modified.aspx . Gotta love their newsletter  

(ps. se poate optimiza si mai mult de atat...dar nu prea are rost )

Edited by zoopp, 10 November 2010 - 17:07.

@zoop: pt. p = 25 formula ta returneaza TRUE. Mai bine zis, pentru orice nr. p astfel incat p % 24 = 1, formula ta e true.