liczby pierwsze!! Opcje

[Buby]

nie wiem jak napisac taki skrypt ktory pokazywalby liczby pierwsze z przedzialu od 0 do n! Prosze o pomoc!!

[Draugfor]

http://mpp.qs.pl/XAlgorytmy/AlgPierwsze.html

[czachor]

http://forum.php.pl/viewtopic.php?t=9193

[Buby]

thx... ale chodzilo mi bardziej o metode php.. a nie TP albo cos inengo!!
bo nie mam zielonego pojecia jak to w php napisac i mi nie chodzi o sprawdzenie jednej liczby tylko wyswietlenuie liczb pierwszych z przedzialu od 0 do n

[czachor]

a przejrzałeś dokładnie ten topic, który wyżej zapodałem?

[Buby]

Przeczytalem to.. i dalej nie doszedlem do tego jak to zrobic Prosze przynajmniej o liste co mam zrobic zeby to napisac

[matys]

Masz tutaj algorytm, czly dokladnie rozpisane co trzeba zrobić:

Kod

Przykład:

Odnajdziemy za pomocą sita Eratostenesa wszystkie liczby pierwsze z zakresu od 2 do 30.

Zapisujemy kolejno wszystkie liczby w tabeli.







2|3 |4 |5 |6 |7 |8 |9 |10| 11| 12| 13| 14| 15| 16| 17| 18| 19| 20| 21| 22| 23| 24| 25| 26| 27| 28| 29| 30 |





Teraz bieżemy pierwszą liczbę z tabeli (2) i począwszy od następnej (3) dzielimy przez nią wszystkie kolejne liczby. Te, które są przez nią podzielne wykreślamy z niej.





2 3   5   7   9   11   13   15   17   19   21   23   25   27   29  





Bieżemy kolejną liczbę (3) i dzielimy przez nią pozostałe liczby począwszy od następnej (5, bo 4 już jest wykreślone). Podzielne wykreślamy z tabeli.





2 3   5   7       11   13       17   19       23   25       29  





Kolejną liczbą w tabeli jest 5. Postępujemy jak poprzednio.





2 3   5   7       11   13       17   19       23           29  





W tym momencie możemy zakończyć nasze poszukiwania. Algorytm "mówi", że kolejne wykreślania należy powtarzać, nie dalej jak do liczby będącej zaokrąglonym w dół pierwiastkiem zakresu. U nas jest to: sqrt(30)=5.4772255.., po zaokrągleniu w dół otrzymujemy 5. W tabeli zostały już tylko liczby pierwsze.

[BzikOS]

Skrypty => php

[DhuCerbin]

wzory na liczby pierwsz są :-)

wzory Wormella, Willansa ...

wzorów nie przytocze bo podręczniki zostały na kwadracie :/

[NuLL]

Wydaje mi sie ze php jest na tyle szybkie i jesli n nie jst za duze to mozna zrobic petle i sprawdzac czy liczba jest pierwszei ew. wypisac

[maulus]

[php:1:bb88335151]<?php

$intX = 10000; // ilosc liczb do przecedzenia przez sito
$arrPrimes = range( 1, $intX );

for( $i = 2; $i <= $intX; $i++ )
{
$z = 2;

while( $i * $z <= $intX )
{
unset( $arrPrimes[ array_search( ( $i * $z ), $arrPrimes ) ] );
$z++;
}
}


?>[/php:1:bb88335151]


ktoś już pisał ten kod na forum bodajże cudi..

[NuLL]

O cos takiego mi chodzi dla poczatkujacego najlatwiej mi sie wydaje. nie wiem jak wy

[talee]

Bierzemy sobie kolejno kandydatów i próbujemy dzielić przez liczby pierwsze, które trzymamy w tablicy. Jeżeli się podzieli to ne jest pierwsza w przeciwnym wypadku est. Dzielimy tylko przez te liczby pierwsze spełniające warunek pierwsza * 2 <= kandydat.

[php:1:455022dbeb]<?php

// funkcja wypisuje wszystkie liczby
// pierwsze z zakresu od [1..$zakres]

function pierwsze($zakres) {

if ($zakres >= 2) {
echo '1 -> 2', "n";
$tab_pierwsze[] = '2'; // eliminujemy przypadek trywialny
}

$tab_pierwsze_count = 1;

$j = 2;

for ($i = 3; $i <= $zakres; $i++) {

$pierwsza = true;
$sqrt = floor(sqrt($i)) + 1;

for ($k = 0; $k < $tab_pierwsze_count; $k++) {
if ($i % $tab_pierwsze[$k] == 0) {
$pierwsza = false; // nie jest pierwsza
break;
}
if ($tab_pierwsze[$k] > $sqrt) {
break; // nie dzielimy przez p, takie że 2 * p > i
}
}

if ($pierwsza) {
$tab_pierwsze[] = $i;
++$tab_pierwsze_count;
echo "$j -> $in";
++$j;
}
}
}
?>[/php:1:455022dbeb]