Най-добрият начин да проверите дали едно число е просто е да видите дали се дели на някое просто число преди него. Pi(x) е този, който продължавам да виждам навсякъде... Можете да видите малко повече информация за простото броене на wikipedia.
Така че най-ефективният начин, за който се сещам в момента, е следният:
class prime
{
public $primes = [ 2, 3, 5, 7 ];
public $not_prime = [ 1, 4, 6, 8, 9 ];
public function is_prime( int $n )
{
if ( $n <= 1 ) return false;
if ( in_array( $n, $this->primes ) ) return true;
if ( in_array( $n, $this->not_prime ) ) return false;
for( $i = 0; $i < count( array_slice( $this->primes, 0, $this->prime_count( $n ) ) ) || $i == $n; $i++ )
{
if ( $n % $this->primes[ $i ] == 0 ) return false;
}
return true;
}
public function build_primes_to( int $n )
{
for ( $i = end( $this->primes ) + 1; $i <= $n; $i++ )
{
if ( $this->is_prime( $i ) )
{
$this->primes[] = $i;
}
else
{
$this->not_prime[] = $i;
}
}
}
public function prime_count( $n )
{
$ln = log( $n );
if ( $ln == 0 ) return 1;
return intval( ceil( $n / $ln ) );
}
}
Което всъщност не е много ефективно, добре, не и когато става дума за съставяне на списък с прости числа... Работя върху по-добър начин за съставяне на списъка тук, въпреки че би било също толкова лесно и много по-ефективно да намерите списък онлайн и да го използвате.
Използването на горното би било по следния начин:
$find_to = 1000;
$prime = new prime();
$prime->build_primes_to( $find_to );
print "<pre>";
for ( $i = 1; $i < $find_to; $i++ )
{
print "$i is " . ( !$prime->is_prime( $i ) ? "not " : "" ) . "prime\n";
}
person
Alexander Holman
schedule
12.10.2016