Php cam lent!!

[Pr0tecT0R]

Nush daca e doar compul meu care le Procesor PIV la 3 GHz e lent sau e lent asa in general php`u.
Am facut un script ca sa afiseze toate numerele prime pana la o valoare data ... am incercat un script de numere prime facut de mine care l-am invatat prin clasa a IX-a :P nush cat de eficient e .probabil sunt eu buba pentru ca este php asa de lent... sau chiar nu exista un algoritm mai eficient de cat esta?nu am zis ca e cel mai eficient de aia am si postat ca sa veniti fiecare cu cate o idee de numere prime ...deci eu vreau ca sa se poata ganera de exemplu toate numere prime de la 2 pana la 600000 de exemplu intr-o secunda.. daca aveti alta varianta de script in php. sau alt limbaj de programare ..:P ps:Stiu de la scoala doar Pascalu asa ca nu ma sfatuiti cu Pascal sau C++ ca nu mi se pare interesant Ziceti ceva de genu VB sau JS sau ... ASP sau cine stie..
COD

<?php
if (isset($_POST['nr']))
	{
	$nr=$_POST['nr'];
	$i=2;
	while ($i <= $nr)
		{
		$ok=true;
		$j=2;
		while (($j <= sqrt($i))&&($ok))
			{
			if ( $i % $j == 0)
				{
				$ok=false;
				break;
				}
			else $j++;
			}
		if ($ok)
			echo 'Numarul : '.$i.'';
		$i++;
		}
	}
?>
<form action='prime.php' method='POST'>
<table border= '0'>
<tr>
<td>Dati Numarul:</td>
<td>
<input type='text' name='nr'>
</td>
<td>
<input type='submit' value='OK'>
</td>
</tr>
</table>
</table>
</form>

cam asta e cu formular cu tot
astept indicatii sau solutii ... oricum daca dau 600000 imi trece de 30 de secunde timeout

[Pr0tecT0R]

e prea grea problema sau ?ziceti ma chiar nu stiti un algoritm mai eficient de numere prime decat cel postat de mine ? nu ma refeream neaparat de php sau nu ma refeream neaparat de acest algoritm deci vreau sa afisez 600.000 de numere prime in mai putin de 3 secunde ... sa vedem care este primu venit cu un astfel de algoritm .. .ii raman dator si recunoscator poate nu cine stie ce dar ma framanta ... problema asta pentru ca trebuie sa existe ... un algoritm mai eficien care sa afiseze peste o jumatate de milion de numere prime ... in mai putin de 3 secunde.. in fine eu o sa astept in continuare ) daca nu gasesc rezolvare :kill: sau ii scriu la sa-mi aduca de craciun algoritmul !!!

[Synax_]

Cod PHP:

<?php

function prim($x) {
$nd = 0;
$y = $x / 2;
for ($i=1; $i<=$y; $i++)
  if ($x % $i == 0) $nd++;
if ($nd == 0) return TRUE;
else return FALSE;
}

?>

asta il stiu dintr-a cincea

[Synax_]

uite si unu recursiv daca asta nu te satisface


function prim($x,$d) {
if ($d == 1) return TRUE;
elseif ($x % $d == 0) return FALSE;
else prim($x,$d-1);
}


//si il apelezi if (prim($un_numar,$un_numar/2))
?>

[Pr0tecT0R]

mda astai si mai in sus postat de mine chiar mai eficient e al meu oricum al tau verifica doar daca un numar este prim .. :P fa unu ca mine adica sa afiseze toate numerele prime de la 2 pana la ... un numar de ordinilor sutelor de mii si vezi cat timp iti ia pana le afiseaza pe toate daca reusesti sa faci unu care sa afisese peste 500.000 de numere prime de la 2 la 500.000 mai bine zis in mai putin de 3 secunde toata lauda mea si stima oricum o sa mai incerc .. sa vedem si apropo in a-5a nush zau daca stiai ce-i aia informatica :P oricum ... ma bucur ca totusi a raspuns cineva la aceasta problema dar totusi astept raspuns in continuare ...

[Synax_]

pai banuiesc ca tu cauti un nr prim intr-un sir si il afisezi nu?

cred k cea mai rapida metoda sa faci asta e recursiv cu divite et impera daca asa se scrie dar trebuie sa le ordonezi crescator (cel mai bine tot cu divide et impera) nu stiu daca o sa ajung la ceva asa record cum ai zis u dar o sa incerc.
si daca vrei sa mearga si mai repede mai faci 3 functii
- daca ultima cifra e para (sa vezi daca e par)
- una sa vezi daca suma cifrelor este divizibila cu 3 (sa vezi daca e div cu 3)
- suma cifrelor de pe pozitii pare minus suma cifrelor de pe pozitii impare sa fie divizibila cu 11(asta inseamna k numarul e div cu 11)

si asa elimini mai rpd niste nr.

[Pr0tecT0R]

hmm idei bune ... oricum o sa incerc .. sa fac un astfel de cod mai trebuia faza cu daca ultima cifra e 0 sau 5 atunci e divizibil cu 5 :P oricum is mai multe functii inca ceva... eu VREAU TOATE NUMERELE PRIME PANA LA 500.000 ... nu-mi trebuie doar unu !!! imi trebuie sa generez toate numerele pana la 500.000 in mai putin de 3 secunde!!!!SPER CA AI INTELES :P nu vreau sa le aranjez sau alte chestii doar sa le generez .. restu stiu eu ce am de facut :P oricum daca vrei iti zic problema ... sa vedem daca o rezolvi .. sau mai bine zis daca o rezolva cineva.. ) is tare curios ca eu ma chinui de cateva lunii adica .. am cam lasat-o balta dar .. acuma mam reapucat de ea:P

[Synax_]

da uitasem vezi cum iese la iveala

pai e perfect atunci deci e cu un for i de la 1 la 500 000 si aplici pt fiecare nr

in ordine functia pt ultima cifra para dupaia functia pt ultima cifra 0 sau 5 dupaia cea cu 3 su dupaia cea cu 11.

te descurci cu divite et impera sau sa te ajut?

[Synax_]

da zi-mi si problema ca sunt curios

[Pr0tecT0R]

ma descurc cu orice deci iti mai zic inca o data nu is incepator :P ... oricum ms de ajutor .... oricum nu vad la ce mi-ar trebuii devide-t impera? ...sau ? daca fac functiile alea de 0 sau 5 la sf sau daca suma cifrelor se imparte la 3 sau daca ... suma cifrelor de pe pozitii pare minus suma cifrelor de pe pozitii impare sa fie divizibila cu 11(asta inseamna k numarul e div cu 11) nush la ce mar ajuta devide-t impera ca eu un string de 6 cifre :P merge repede ... daca te gandeai la asta.. oricum nam chef acuma sa rezolv problema asta poate maine sau cand is mai proaspat mintal ... nu-ti zic inca problema ca poate-o faci si ma fac de ras ... ma chinui eu un pic .. u prima data fa probl asta si dupaia ... trecem la pasii urmatori .. oricum problema intraga trebuie sa faca 3 chestii foarte grele in 3 secunde prima chestie e faza cu generarea toate numerelor prime pana la 600.000 aprox.. oricum un numar peste 500.000 oricum mai vb .. apropo cati ani ai ... ?

[Synax_]

am 17 d c?
divide et imper. e un altgoritm de cautare mai rpt. cauta din jumate in jumate. in fine nu prea te ajuta aici ai dreptate dar la cautare te ajuta super mult e super eficient.

[Pr0tecT0R]

ahaha nu ma trata ca pe un nestiutor pls ... ca sunt mai batran ) stiu ce-i aia divide et impera doar nus de ieri .. ti-am zis ca nu am ce sa caut pe aici ... asa ca ... ce sa fac cu devide et impera ... deci sper sa rezolv faza cu numerele prime.. oricum functiile tale tot nu cred ca is de ajuns .. de ex cum verifici daca un numar se imparte la 5 ... rasp:daca are la sfarsit 0 sau 5 ... cum verifici daca un numar se imparte la 7 ?? cum verifici daca un numar se imparte la 11 :rasp lai dat tu : cum verifici daca se imparte la 13 cum verifici daca un numar se imparte la 17 cum verifici daca se imparte la 19 ... si asa mai departe .. deci tot la algoritmul vechi ajungi ... doar ca cine stie ... te ajuta cat de putin .. cateva functii ... in fine .. tot the oldies are the bests... ce crezi ca suntem primi care ne gandim la algoritmi de numere prime ? cine stie poate facem cel mai aficient algoritm revolutionam algoritmu de numere prime sau nu!

[Synax_]

pai nu te-am tratat ca pe un incepator(sper k pot sa folosesc pers 2 sg ) si imi cer scuze daca am lasat impresia asta. si uite intre timp mi-a mai venit o idee. deci numerele pare cu cat sunt mai mari cu atat sunt intervale mai mari intre ele si ai putea sa afli unde sunt intervalele respective si mai sari cate 10 100 ...


da si sper sa il facem pe cel mai eficient

[Pr0tecT0R]

din fraza asta "divide et imper. e un altgoritm de cautare mai rpt. cauta din jumate in jumate. in fine nu prea te ajuta aici ai dreptate dar la cautare te ajuta super mult e super eficient." mai tratat ca pe un incepator oricum nu sunt eu nici as dar ce e divide et impera mai stiu si eu de prin cls a X-a.. sau a IX-a nu mai stiu ... in fine acuma ma duc sa dorm ca is rupt mai ... ma gandesc pana maine ... la tot felu de idei si sper sa apara si altii cu idei ... am sa propun si alte probleme de genu asta pentru ca ... atunci cand citesc o problema si nu o rezolv imi vine sa ma impusc ... deci nu ma las pana nu rezolv o problema citata ) "mama mi-a interzis sa mai citesc probleme al informatica" =)) glumeam ...
hai ca te las acum nb.. .mai ma gandesc pana maine si ... poate vin si cu niste functii si poate chiar cu codul cel mai eficient !

[Synax_]

bine poate acolo putin de tot(nesemnificativ) dar fara sa vreau si imi cer mi de scuze
nb si spor la lucru

[Pr0tecT0R]

np nu trebuie sa-ti ceri scuze :!) nb si tie .

[outkast]

uite un algoritm care mi-a placut mie:

Cod PHP:

<?php
$startTime = explode(' ',microtime()); //cand incepe

$n = 140000;  //pana la ce nr se duce
$a = array();

$a[1] = 0;
//flaguri 1 = prim, 0 = neprim, pp ca sunt toate prime
for($i = 3; $i<=$n; $i+=2) $a[$i] = 1;  
$p = 3;
while($p*$p <= $n)   //sqrt($n) e max dar fac asa pt ca p*p e mult mai rapid
{
    $j = $p*$p;
    while($j <= $n)
    {
        $a[$j] = 0;
        $j = $j+$p;
    }
    do {$p+=2; }while($a[$p] == 0);
}

foreach($a as $ind => $val)
{
 //indecsi reprezinta nr prime, valorile sunt doar flaguri
    if($val == 1)    echo "$ind"; 
}


$endTime = explode(' ',microtime());
$runtime = (float)$endTime[0]+(float)$endTime[1] - (float)$startTime[0]-(float)$startTime[1];
printf('runtime: %.10f',$runtime);

?>

e destul de rapid dar mananca o gramada de memorie.
se duce doar pana la 140 000 pt ca depaseste limita de memorie pe xhost. mai merge optimizat destul de mult.

sper sa fie scris bine ca sunt destul de obosit .
/edit: am modificat putin codul pt ca nu imi placea cum calculeaza timpul de rulare, acum cred ca e mai bine

[indy2kro]

PHP nu prea e extraordinar de rapid, pt aplicatii de genul asta ti-as recomanda ... clasicul C (al' de DOS) .. simplu, rapid, eficient (excelent pt probleme inutile gen sa generezi toate numerele prime sau variatiuni pe aceeasi tema).

[Pr0tecT0R]

tocmai asta e ca nu stiu asa de bine c++ pt .. si totusi vroiam sa fac in php chestia asta oricum lucrez la un algoritm foarte eficient :P sper sa fie si cat de cat cel mai eficient ... in curand o sa-l postez sa vedem daca aveti unu mai eficient .. cel de mai in sus nush cat de eficient e ca nu am avut timp sa-l testez inca dar o sa-l testez si o sa verific

[indy2kro]

Daca stii PHP in principiu tot ce trebuie sa faci este sa scoti $ din fata variabilelor si sa definesti variabile (cu tot cu tip) .. chiar nu este asa mare greutate.