Мне нужно найти простые числа для цикла или цикла while
Я написал это, но это неправильно
<?php
$i = 1;
while($i<5)
{
for($j=1; $j<=$i; $j++)
{
if ($j != 1 && $j != $i)
{
echo $i . "/" . $j . "=" . $i%$j . "<br />";
if ($i%$j != 0)
{
echo $i . "<br />";
}
}
}
echo "<br />";
$i += 1;
}
?>
Есть ли способ разделить число с массивом, чтобы найти оставшиеся?
Вот небольшая функция, которую я нашел: (http://icdif.com/computing/2011/09/15/check-number-prime-number/) Казалось, что я работаю для меня!
function isPrime($num) {
//1 is not prime. See: http://en.wikipedia.org/wiki/Prime_number#Primality_of_one
if($num == 1)
return false;
//2 is prime (the only even number that is prime)
if($num == 2)
return true;
/**
* if the number is divisible by two, then it not prime and it no longer
* needed to check other even numbers
*/
if($num % 2 == 0) {
return false;
}
/**
* Checks the odd numbers. If any of them is a factor, then it returns false.
* The sqrt can be an aproximation, hence just for the sake of
* security, one rounds it to the next highest integer value.
*/
$ceil = ceil(sqrt($num));
for($i = 3; $i <= $ceil; $i = $i + 2) {
if($num % $i == 0)
return false;
}
return true;
}
Вы можете использовать эту функцию PHP gmp_nextprime()
Это базовая реализация:
function prima($n){
for($i=1;$i<=$n;$i++){ //numbers to be checked as prime
$counter = 0;
for($j=1;$j<=$i;$j++){ //all divisible factors
if($i % $j==0){
$counter++;
}
}
//prime requires 2 rules ( divisible by 1 and divisible by itself)
if($counter==2){
print $i." is Prime <br/>";
}
}
}
prima(20); //find prime numbers from 1-20
Это будет выводить
2 is Prime
3 is Prime
5 is Prime
7 is Prime
11 is Prime
13 is Prime
17 is Prime
19 is Prime
Полная пошаговая логическая и визуальная аналогия здесь: здесь
Вот один лайнер, который я нашел некоторое время назад, чтобы проверить простые числа. Он использует метки табелирования (унарная математика) для определения:
function is_prime_via_preg_expanded($number) {
return !preg_match('/^1?$|^(11+?)\1+$/x', str_repeat('1', $number));
}
Проверять все числа последовательно для простых чисел:
$i=2; // start here (2 is the first prime)
while (1) { // neverending loop
if (is_prime_via_preg_expanded($i)) echo $i." <br />\n";
$i++;
}
Чтобы проверить только ряд чисел для простых чисел, как в приведенном примере:
$start = 2; // start here (2 is the first prime)
$end = 100;
$i=$start;
while ($i<=$end) {
if (is_prime_via_preg_expanded($i)) echo $i." <br />\n";
$i++;
}
Без математической функции:
function isPrimeNumber($i) {
$n = 2;
while ($n < $i) {
if ($i % $n) {
$n++;
continue;
}
return false;
}
return true;
}
Я знаю, что уже слишком поздно, но я обнаружил, что это решение более элегантно.
function isPrime($num)
{
if ($num < 2) {
return false;
}
for ($i = 2; $i <= $num / 2; $i++) {
if ($num % $i == 0) {
return false;
}
}
return true;
}
Все, что sqrt() является ложным или любое значение float является простым числом
Это, я считаю, довольно эффективная процедура, в которой перечислены все простые числа до 1000.
Он проверяет каждое число ($ x), чтобы увидеть, есть ли у него какие-либо факторы (кроме него и 1, конечно).
Математически нет необходимости проверять все более низкие числа как возможные факторы, только нижние простые числа до квадратного корня из $x. Это активируется путем хранения простых чисел, поскольку они находятся в массиве (который, я думаю, является стратегией, к которой ссылался OP).
Как только будет найден первый простой коэффициент, мы знаем, что $x не является простым, и поэтому дальнейшее тестирование этого значения $x не требуется, и мы можем выйти из цикла foreach.
$primes = array();
for ($x = 2; $x <= 1000; $x++) {
$xIsPrime = TRUE;
$sqrtX = sqrt($x);
foreach ($primes as $prime) if ($prime > $sqrtX || ((!($x % $prime)) && (!$xIsPrime = FALSE))) break;
if ($xIsPrime) echo ($primes[] = $x) . "<br>";
}
Sieve_of_Eratosthenes - простой и быстрый алгоритм для нахождения простых чисел.
function getPrimes($finish)
{
$number = 2;
$range = range($number,$finish);
$primes = array_combine($range,$range);
while($number*$number < $finish){
for($i=$number; $i<=$finish; $i+=$number){
if($i==$number){
continue;
}
unset($primes[$i]);
}
$number = next($primes);
}
return $primes;
}
<?php
$n = 11;
$o = $_POST["maxprime"];
echo 'The script calculated the next primenumbers:</br>';
echo '2, 3, 5, 7, ';
while (true) {
$t = 6;
while (true) {
if ($n % ($t - 1) == 0) {
break;
}
if ($n % ($t + 1) == 0) {
break;
}
if ($t > sqrt($n)) {
echo("$n, ");
break;
}
$t += 6;
}
if (($n + 1) % 6 == 0) {
$n += 2;
} else {
$n += 4;
}
if ($n > $o) {
break;
}
}
?>
Я знаю, что это происходит поздно, но надеюсь, что это поможет кому-то.
function prime_number_finder($range)
{
$total_count=0;//intitialize the range keeper
$i=1;//initialize the numbers to check
while ($total_count<=$range)
{
$count=0;//initialize prime number inner count
$k=$i;
while ($k!=0)
{
if(($i%$k)==0)
{
$count++;
}
$k--;
}
//condition to check if a number is prime
if($count==2 || $count==1)
{
echo $i."</br>";//output the prime number;
$total_count++;
$i++;
}
//number is not prime
if($count>2)
{
//$total_count++;
$i++;
}
}
}
//пример prime_number_finder (200);
$n = 7;
if ($n == 1) {
echo 'Not a Prime or Composite No.';
}
$set = 0;
for ($index = 2; $index <= $n/2; $index++) {
if ($n % $index === 0) {
$set = 1;
break;
}
}
if ($set) {
echo 'Composite';
} else {
echo 'Prime';
}
Найдите простые числа от 1 до 10000, используя закрытие в array_filter():
$start = 2;
$step = 10000;
$stop = $start + $step;
$candidates = range($start, $stop);
for($num = 2; $num <= sqrt($stop); ++$num){
$candidates = array_filter($candidates,
function ($v) use (&$num){
return ($v % $num) != 0 || $v == $num ;
}
);
}
print_r($candidates);
Изменить: 1 не является простым числом
Лучший способ проверить, является ли число простым, - это увидеть, если он делится на любое простое число перед ним. Pi (x) - это тот, который я все время вижу повсюду... Вы можете увидеть немного больше информации о Prime Counting on 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";
}
Я знаю, что это немного поздно, но здесь простая программа, которая поможет вам сделать то, что вы просите...
<?php
//Prime Function
function fn_prime($number) {
$i = 2; $result = TRUE;
while($i < $number) {
if(!($number%$i)) {
$result = FALSE;
}
$i++;
}
return $result;
}
//Declare integer variable...
$k = 0;
//Start Loop up to any number of your choice for e.g. 200
while($k < 200) {
if(fn_prime($k)) {
echo "$k is a prime number<br/>";
} else {
echo "$k is not a prime number!<br/>";
}
$k++;
}
?>
<?php
function prime_number($num){
for( $j = 2; $j <= $num; $j++ )
{
for( $k = 2; $k < $j; $k++ )
{
if( $j % $k == 0 )
{
break;
}
}
if( $k == $j )
echo "Prime Number : ".$j."<br>";
}
}
prime_number(23);
?>
Расширенная версия ответа @Farkie, сделанная специально для проверки простых чисел в циклах.
function isPrime_v2($num) {
static $knownPrimes=[3]; // array to save known primes
if($num == 1)
return false;
if($num == 2 || $num == 3) //added '3'
return true;
if($num % 2 == 0)
return false;
$ceil = ceil(sqrt($num)); //same purpose, good point from Farkie
// Check against known primes to shorten operations
// There is no sense to check agains numbers in between
foreach($knownPrimesas $prime){
if ($prime>$ceil)
break;
if($num===$prime)
return true;
if($num % $prime == 0)
return false;
}
/**
* end($knownPrimes) % 2 !==0 - mathematically guaranteed
* start with latest known prime
*/
for($i = end($knownPrimes)+2; $i <= $ceil; $i = $i + 2) {
if($num % $i == 0)
return false;
}
$knownPrimes[]=$num;
return true;
}
Тест с phpfiddle.org. V1 - ответ Farkie, V2 - расширенная версия
V1 (1 to 5,000,000): divisions=330 929 171; primes=348 513; time=21.243s
V2 (1 to 5,000,000): divisions=114 291 299; primes=348 513; time=10.357s
Функция NOTE!
isPrime_v2применима ТОЛЬКО в случае цикла из 3. В противном случае сохраненный массив $knownPrimes будет иметь недостаточную историю.
Вот еще один очень простой, но тихий эффективный подход:
function primes($n){
$prime = range(2 , $n);
foreach ($prime as $key => $value) {
for ($i=2; $i < $value ; $i++) {
if (is_int($value / $i)) {
unset($prime[$key]);
break;
}
}
}
foreach ($prime as $value) {
echo $value.'<br>';
}
}
primes(1000);
<?php
$limit=100;
$i=1;
outer:while($i<=$limit){
$j=2;
while($j<$i){
if($i%$j==0){
$i++;
goto outer;
}
$j++;
}
echo $i;
echo "<br/>";
$i++;
}
?>
Программа ниже проста с двумя циклами for и игнорирует 1 и собственные значения в итерации. Он напечатает простые числа,
function get_primenumbers($length) {
//Ignore 1
for($i = 2; $i <= $length; $i++){
$prime = true;
for($j = 2; $j <= $i; $j++){
//Ignore same number
if(($i != $j) && ($i % $j == 0)){
$prime = false;
break;
}
}
if(!$prime){
echo "$i is not prime <br />";
}else{
echo "$i is prime <br />";
}
}
}