Prosze o pomoc!!
Pełna wersja: liczby pierwsze!!
nie wiem jak napisac taki skrypt ktory pokazywalby liczby pierwsze z przedzialu od 0 do n! Prosze o pomoc!!
Prosze o pomoc!!
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 
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
a przejrzałeś dokładnie ten topic, który wyżej zapodałem?
Przeczytalem to.. i dalej nie doszedlem do tego jak to zrobic Prosze przynajmniej o liste co mam zrobic zeby to napisac
Prosze przynajmniej o liste co mam zrobic zeby to napisac
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.
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.
Skrypty => php
wzory na liczby pierwsz są :-)
wzory Wormella, Willansa ...
wzorów nie przytocze bo podręczniki zostały na kwadracie :/
wzory Wormella, Willansa ...
wzorów nie przytocze bo podręczniki zostały na kwadracie :/
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
[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..
$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..
O cos takiego mi chodzi dla poczatkujacego najlatwiej mi sie wydaje. nie wiem jak wy
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]
[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]
To jest wersja lo-fi głównej zawartości. Aby zobaczyć pełną wersję z większą zawartością, obrazkami i formatowaniem proszę kliknij tutaj.