DAU FUNDA! Cine le are la Informatica C++?

Nu stiu cum determini numarul elementelor prime dintr-un vector ( v[30] ) in c++. Ma poate ajuta cineva? Funnndaaa!

Fa-ti o functie care testeaza daca un numar e prim,si aplici functia pe fiecare element din vector. Apoi iti iei un contor, si pui un if:
Daca functia determina ca e prim, contorul creste si trece la urmatorul element, daca nu, doar trece la urm. element.

Ai facut functiile?

#include
void main()
{int numar, i, s;
s=0;
coutnumar;
for(i=1; i

Http://pastebin.com/vPrtvRMx

Da-mi funda ca le am.

Nu e ideea cea mai eficienta
Practic n-ai nevoie de vector, presupunand ca ai un N citit de la tastatura si un vector cu N numere poti face direct de la citirea "vectorului" verificarea daca e prim dar daca tii sa scrii mai mult si sa-l faci si mai ineficient atunci il faci cu vector

Pt prim verifici daca nr e par, daca da, nu e prim altfel iei un contor de la 3 pana la radical din nr cu pas2 (pentru a elimina contorul pozitiv) si incepi sa verifici daca nr tau se imparte la contor
Daca numarul nu s-a impartit la contor atunci incrementezi o variabila pe care o afisezi la sfarsit.


Ideea ar fi cam asa:

int p(int x)
{int i; if(! x%2)return 0; for(i=3; i>n;
for(i=0; i>x; v[i]=x; }
for(i=0; i

Ce face if(! x%2)return 0;?

Daca x este par (restul impartirii la 2 = 0) functia returneaza 0 (fals)
Asa ar fi cea mai eficienta metoda pentru ca la:
x= 1, 000, 000, 001
metoda cu "pentru i=2, n dc x mod i = 0 return 0" parcurge 1, 000, 000, 000 iar cu sqrt parcurge 32 mii si metoda mea doar 15 mii
M-am uitat si pe sursa lui raindrops, daca obs trebuie sa pa rcurga pentru x de mai sus, 1 miliard de numere, atribuiri si comparatii. ( pentru i=1 i

Daca x este par (restul impartirii la 2 = 0) functia returneaza 0 (fals)
Nu cred ca face asta. Ai testat cumva?

Asa ar fi cea mai eficienta metoda pentru ca la:
x= 1, 000, 000, 001
metoda cu "pentru i=2, n dc x mod i = 0 return 0" parcurge 1, 000, 000, 000 iar cu sqrt parcurge 32 mii si metoda mea doar 15 mii

"Metoda ta" nu a fost postata pe site. Foloseste pastebin.com ca raindrops.
1, 000, 000, 001 se divide cu 7, dar daca zici ca ai gasit o metoda mai rapida ca sqrt(nr) is curios s-o vad.

Am testat
Daca spui ca se imparte la 7 bine, ideea era ca un nr ff mare prim ar dura mult sa-l verifice.

Daca faci c++ am sa-ti dau o sursa in limbajul de programare s-o testezi ca sa vezi si faza cu functia:


Pentru x = 330000067 pe sursa mea (http://pastebin.com/2nNj9730) am stat mai putin de 1 secunda pentru rezultat, pe sursa lui raindrops (http://pastebin.com/s4yvqvxt) pe acelasi x am stat lejer 6 minute.
Testeaza si vei vedea diferenta.

E de mentionat si urmatorul lucru :
Executarea unui program decurge mai rapid daca nu trebuie apelate functii si toate variabilele sunt locale (se lucreaza mai greu cu cele global) (!)SI functiile de i/o sa fie in C nu in C++ (C lucreaza mai rapid) asta pentru timp de executie mai mic

In postul initial uitasesi o paranteza la if(! x%2)return 0;
Ma rog, dar si 2 e numar prim... dar programelul tau zice ca nu e.
Si int i ala din functie nu cred ca e cea mai inspirata alegere... ce se intampla daca sqrt(x) depaseste 32mii?

Asa e, daca modifici in if( (x%2)==0 && x>2 ) atunci pentru x=2 iti arata ca e prim (ca sa te simti bine)
Si aia cu int i este tot un lucru minor, il faci long int si gata (long long nu are rost pentru ca merge pana la sqrt (asta asa ca sa economisesti si memorie))

Stiai ca in for(i=3; i

Da

Foarte amuzant. Am uitat ca TPU mananca...

Stiai ca in for(i=3; i<=sqrt(x); i+=2), expresia de test i<=sqrt(x) se executa la fiecare iteratie? Adica sqrt(x) e recalculat de fiecare data cand testeaza, indiferent daca x e acelasi sau nu...

Daca tot n-ai inteles lasa-mi id-ul tau sa nu mai facem spam

Da, dar daca observi, cu sau fara, tot imi rezolva problema in mai putin de 0 secunda.
Oricum observatia e buna, dar atata timp cat am scos 6 minute din sursa precedenta este irelevant faptul ca se recalculeaza un radical totul facandu-se in

Foloseste site-ul asta ca sa iti faca escape la < > ca altfel iti mananca tot comentariul
http://www.htmlescape.net/htmlescape_tool.html

Numai debifeaza "Replace newline with "

Da, am vazut ca iti merge mai repede programelul tau, dar atat timp cat poate fi imbunatatit mai mult... credeam ca te-ar interesa.
Si spam nu prea cred ca facem. Cel care a pus intrebarea sigur nu mai e peaici.

Si asa am transformat in chat.
In fine, m-am plictisit de o tampenie de prim.
Daca vrei sa stam la "taclale" de informatica arata-mi ceva interesant nu cum se verifica un nr prim (de clasa a5-a)

Facand chestii aparent simple inveti cel mai mult... dar daca tu zici.
Exista metode mai rapide de a afla sqrt decat cea din math.h
De exemplu, in programarea grafica e nevoie foarte des sa normalizezi vectori. Si formula respectiva implica extragerea unui radical (sqrt), mai exact sqrt^-1. Dar sqrt e o functie foarte inceata si costisitoare. Daca o folosesti de cateva milioane de ori pe secunda se duce fps-ul jocului in jos. Asa ca au folosit o aproximare a lui sqrt^-1.
De asemenea, exista si metode mai rapide de a afla sqrt, nu doar sqrt^-1
Uite:
http://en.wikipedia.org/wiki/Fast_inverse_square_root
http://www.codeproject.com/......on-Precisi
Asta ti se pare interesant?

Ai putea de exemplu, sa faci un programel care afiseaza primele n numere prime din sirul lui fibonacci, in ordine descrescatoare? (de clasa a cata ti se pare asta?)

Da, mi se pare interesanta faza cu radicalul
Programul cu n nr prime din sirul lui fibonacci e usor de facut, dar in momentul de fata daca l-as face, l-as face ineficient (prima ideea ce mi-a venit fu sa pun fiecare nr din sir pe vector si sa-l afisez descrescator) dar probabil ca exista si o formula sa le gasesti descrescator.

Apropo de chestia cu prim, mai exista o formula ciudata (daca suntem la capitolul "interesant"):
if (!(x % (x-1)! + 1)) atunci x este prim

Ideea cu pusul in vector pare cea mai ok.
Ai putea sa folosesti functii/stiva pentru a afisa numerele recursiv, dar asta o sa fie mai inceata pentru n mare.
Dar daca chiar vrei sa optimizezi si exercitiul asta, iti mai dau un hint: eu m-as uita la formula F(n-2)=F(n)-F(n-1) de aici http://en.wikipedia.org/wiki/Fibonacci_number

if (!(x % (x-1)! + 1)) atunci x este prim
Si ce marja de eroare are chestia asta? Pentru ce fel de numere merge? Chiar arata ciudat rau :))

Am gasit intr-o carte de algoritmi sub numele de "Algoritmul lui Wilson" dar e cam ineficient si nu merge pe numere mari (are un factorial acolo)

Daca insisti cu fibonacci fa-l tu recursiv si eu pe vector si vedem care-i mai rapid.
De fapt cea mai usoara cale (cum sirul lui fibonacci nu merge prea extins pe long long int) este sa faci un vector initiat cu valorile din sir.

Eu ma refeream doar la afisare sa fie recursiva, ca sa nu trebuiasca vector pentru a fi afisate descrescator. Dar si asta o sa fie inceata pentru multe numere de afisat...

Nu stiu la ce te referi.
Ai spus numerele prime din sirul lui fibonacci afisate descrescator, eu doar atat am scris: http://pastebin.com/82XRa5ut

Ehm, ideea era sa le calculezi tu. Nu sa le faci copy paste intr-un vector si sa le afisezi. Asta poate sa faca oricine.

Stii sa implementezi operatii pe numere mari?

Nu, enuntul dat de tine spune clar sa afisezi numerele prime din sirul lui fibonacci in ordine descrescatoare. Nicidecum sa nu folosesc un vector prestabilit sau sa calculez intr-un mod anume numerele. Ai precizat "afisaza".
Dar asa cum am calculat acele numere din vector asa le pot pune in sursa si putem considera problema rezolvata (iar timpul de executie este sub 1s cu mult)