php проверка числа на простоту

Поиск простых чисел на PHP

Простые числа — это натуральные числа больше 1, которые делятся только сами на себя или на 1. Часто возникающая (например, при шифровании данных) задача — найти все простые числа от 2 до заданного N. Для этого придумано несколько алгоритмов разной эффективности. Давайте рассмотрим их реализацию на PHP.

Простой перебор делителей

Это простейший и наименее эффективный алгоритм из рассмотренных. Для небольших чисел, однако, он вполне применим.

Суть алгоритма: мы просто последовательно перебираем все числа от 2 до N и проверяем, простые они, или нет. Функция проверки на простоту перебирает все нечетные числа от 2 до квадратного корня из N и, если находит такое, на которое N делится без остатка, то число считается составным, а если не находит, то простым.

Эффективность такого алгоритма: O(n * sqrt(n))

Решето Эратосфена

Этот алгоритм как бы «просеивает» все числа от 0 до максимального N через условное решето несколько раз. Сначала последовательно исключаются все числа, кратные 2. Само число добавляется в массив простых чисел. Далее из оставшихся исключаются все числа, кратные следующему простому числу — трем. 4 уже было удалено из исходного массива, соответственно, следом удаляются все числа, кратные 5, и так далее, пока не будут перебраны все числа.

Вот пример решета Эратосфена на PHP:

Метод нахождения псевдопростых чисел с использованием теста простоты Ферма

Данный метод позволяет находить простые числа гораздо быстрее предыдущих двух, однако, это будут псевдопростые числа, то есть числа, которые являются простыми лишь с некоторой (тем не менее, очень высокой, около 100%) вероятностью.

Здесь используется тест Ферма, который гласит: если p-простое число, то если возвести число n в степень (p-1), а потом взять результат возведения в степень по модулю p (остаток от деления на p), то в итоге получится 1.

Вот реализация поиска простых чисел с использованием теста Ферма на PHP:

Эффективность такого алгоритма O(n * log 2 n * log (log n) * log (log (log n)))

Кроме указанных алгоритмов существуют и такие, как:

Кроме того, существует множество тестов простоты числа, как истинных, так и вероятностных. Возможно, в будущем я дополню эту статью реализацией других алгоритмов поиска простых чисел на PHP.

Источник

Простые_числа.php

Поиск простых чисел разными способами. Сравнение алгоритмов поиска простых чисел по памяти и времени.

Подготовка

Записать php 7 в папку c:\php, поместить в эту же папку файл php7.bat со следующим содержимым. Создать папку c:\php\localhost, в неё положить php файлы.

Поиск простых чисел

Перебор простых делителей

Числа проверяются на делимость на простые числа, не превышающие квадратный корень из этого числа. По мере нахождения простых чисел они записываются в массив, который используется для проверки следующих чисел на делимость.

Перебор простых делителей +=2 и 235

Решето Эратосфена

Решето Аткина

Решето Сундарама

Решето Сундарама простое, оно пусть будет домашним заданием.

Результаты

Для сравнения: WinRAR/Меню/Операции/Тест быстродействия, без многопоточности =1200.

Литература

О песочнице

Это «Песочница» — раздел, в который попадают дебютные посты пользователей, желающих стать полноправными участниками сообщества.

Если у вас есть приглашение, отправьте его автору понравившейся публикации — тогда её смогут прочитать и обсудить все остальные пользователи Хабра.

Чтобы исключить предвзятость при оценке, все публикации анонимны, псевдонимы показываются случайным образом.

О модерации

Не надо пропускать:

Источник

is_numeric

(PHP 4, PHP 5, PHP 7, PHP 8)

is_numeric — Проверяет, является ли переменная числом или строкой, содержащей число

Описание

Определяет, является ли данная переменная числом или строкой, содержащей число.

Список параметров

Возвращаемые значения

Примеры

Пример #1 Примеры использования is_numeric()

Результат выполнения данного примера:

Смотрите также

User Contributed Notes 40 notes

If you want the numerical value of a string, this will return a float or int value:

Note that the function accepts extremely big numbers and correctly evaluates them.

So this function is not intimidated by super-big numbers. I hope this helps someone.

PS: Also note that if you write is_numeric (45thg), this will generate a parse error (since the parameter is not enclosed between apostrophes or double quotes). Keep this in mind when you use this function.

for strings, it return true only if float number has a dot

is_numeric( ‘42.1’ )//true
is_numeric( ‘42,1’ )//false

I think that is best check solution if u want to create real calculator for example 🙂

is_number ( 12 ); // true
is_number (- 12 ); // true
is_number (- 12.2 ); // true
is_number ( «12» ); // true
is_number ( «-124.3» ); // true
is_number ( 0.8 ); // true
is_number ( «0.8» ); // true
is_number ( 0 ); // true
is_number ( «0» ); // true
is_number ( NULL ); // false
is_number ( true ); // false
is_number ( false ); // false
is_number ( «324jdas32» ); // false
is_number ( «123-» ); // false
is_number ( 1e7 ); // true
is_number ( «1e7» ); // true
is_number ( 0x155 ); // true
is_number ( «0x155» ); // false
?>

check if given string is mobile number

Referring to previous post «Be aware if you use is_numeric() or is_float() after using set_locale(LC_ALL,’lang’) or set_locale(LC_NUMERIC,’lang’)»:

This is totally wrong!

This was the example code:

——
set_locale(LC_NUMERIC,’fr’);
is_numeric(12.25); // Return False
is_numeric(12,25); // Return True
is_float(12.25); //Return False
is_float(12,25); //Return True
——

— set_locale() does not exist, you must use setlocale() instead
— you have to enclose 12,25 with quotes; otherwise PHP will think that
the function gets _two_ arguments: 12 and 25 (depending on PHP version and setup you may additionally get a PHP warning)
— if you don’t enclose 12,25 with quotes the first argument will be the inspected value (12), the second value (25) is discarded. And is_numeric(12) and is_float(12) is always TRUE

—-
setlocale(LC_NUMERIC,’fr’);
is_numeric(12.25); // Return True
is_numeric(«12,25»); // Return False
is_float(12.25); //Return True
is_float(«12,25»); //Return False
—-

Remarks:
— is_float(12.25) is _always_ TRUE, 12.25 is a PHP language construct (a «value») and the way PHP interpretes files is definitely _not_ affected by the locale
— is_float(«12,25») is _always_ FALSE, since is_float (other than is_numeric): if the argument is a string then is_float() always returns FALSE since it does a strict check for floats

And the corrected example shows: you get the _same_ results for every possible locale, is_numeric() does not depend on the locale.

/* This function is not useful if you want
to check that someone has filled in only
numbers into a form because for example
4e4 and 444 are both «numeric».

I used a regular expression for this problem
and it works pretty good. Maybe it is a good
idea to write a function and then to use it.

$input_number = «444»; // Answer 1
$input_number = «44 «; // Answer 2
$input_number = «4 4»; // Answer 2
$input_number = «4e4»; // Answer 2
$input_number = «e44»; // Answer 2
$input_number = «e4e»; // Answer 2
$input_number = «abc»; // Answer 2
*/
$input_number = «444» ;

The solution is pretty simple and no subroutines or fancy operations are necessary to make the ‘is_numeric’ function usable for form entry checks:

Simply strip off all (invisible) characters that may be sent along with the value when submitting a form entry.

Just use the ‘trim’ function before ‘is_numeric’.

Two simple functions using is_numeric:

?>
And here is the result:
1: odd? TRUE
0: odd? FALSE
6: odd? FALSE
«italy»: odd? FALSE
null: odd? FALSE

1: even? FALSE
0: even? TRUE
6: even? TRUE
«italy»: even? FALSE
null: even? FALSE

Here’s a function to determine if a variable represents a whole number:

just simple stuff.
is_whole_number(2.00000000001); will return false
is_whole_number(2.00000000000); will return true

If you want detect integer of float values, which presents as pure int or float, and presents as string values, use this functions:

Sometimes, we need to have no letters in the number and is_numeric does not quit the job.
You can try it this ways to make sure of the number format:

function new_is_unsigned_float($val) <
$val=str_replace(» «,»»,trim($val));
return eregi(«^(7)+([\.|,](1)*)?$»,$val);
>

function new_is_unsigned_integer($val) <
$val=str_replace(» «,»»,trim($val));
return eregi(«^(7)+$»,$val);
>

function new_is_signed_float($val) <
$val=str_replace(» «,»»,trim($val));
return eregi(«^-?(6)+([\.|,](4)*)?$»,$val);
>

function new_is_signed_integer($val) <
$val=str_replace(» «,»»,trim($val));
return eregi(«^-?(4)+$»,$val);
>

It returns 1 if okay and returns nothing «» if it’s bad number formating.

I needed a number_suffix function that takes numbers with thousand seperators (using number_format() function). Note that this doesn’t properly handle decimals.

Also, increasing the range above the condition statements increases efficiency. That’s almost 20% of the numbers between 0 and 100 that get to end early.

Maybe your function was more strickt, but profides FALSE to any numeric string that wasnt written in the English/American notition. To enable a person to use the both the English/American and the rest of the world’s way:

(*Note:
-the E/A way of writing 1 million (with decimal for 1/50): 1,000,000.02
-the global way of writing 1 million (with decimal for 1/50): 1.000.000,02

Here’s an even simpler pair of functions for finding out if a number is odd or even:

if(IS_ODD($myNumber))
echo(«number is odd\n»);
else
echo(«number is NOT odd\n»);

if(IS_even($myNumber))
echo(«number is even\n»);
else
echo(«number is NOT even\n»);

Results:
number is odd
number is NOT even

Here is a simple function that I found usefull for filtering user input into numbers. Basically, it attempts to fix fat fingering. For example:

The output in this case would be ‘654.45’.
Please note that this function will work properly unless the user fat fingers an extra decimal in the wrong place.

When using the exec() function in php to execute anther php script, any command line arguments passed the script will lose their type association, regardless of whether they are numeric or not, the same seems to hold true for strings as well.

ie : two scripts test.php:

Note that this function is not appropriate to check if «is_numeric» for very long strings. In fact, everything passed to this function is converted to long and then to a double. Anything greater than approximately 1.8e308 is too large for a double, so it becomes infinity, i.e. FALSE. What that means is that, for each string with more than 308 characters, is_numeric() will return FALSE, even if all chars are digits.

However, this behaviour is platform-specific.

In such a case, it is suitable to use regular expressions:

I find it a little weird that people are having issues with ordinal numbers, it’s pretty easy..
Notes are in the commenting, check out the example outputs.

var_dump ( ordinal ( 5 ));

ordinal(‘-1’); returns false because ctype_digit hates anything that
isn’t strictly 0 through 9 and ‘-‘ trips it to false.

ordinal(‘asdf’); returns false for the exact same reason.

ordinal(); returns false because it’s blank.

signed integers on a 32-bit system (and the same issue on a 64-bit
system using 0x7FFFFFFFFFFFFFFF because of two’s compliment,
anything higher will become a negative number):
ordinal(0x7FFFFFFF ); returns 2147483647th (which is correct)
ordinal(0x7FFFFFFF+1); returns false.
*/

Источник

is_int

(PHP 4, PHP 5, PHP 7, PHP 8)

is_int — Проверяет, является ли переменная целым числом

Описание

Проверяет, является ли тип переменной целочисленным.

Список параметров

Возвращаемые значения

Примеры

Пример #1 Пример использования is_int()

Результат выполнения данного примера:

Смотрите также

User Contributed Notes 30 notes

I’ve found that both that is_int and ctype_digit don’t behave quite as I’d expect, so I made a simple function called isInteger which does. I hope somebody finds it useful.

var_dump ( is_int ( 23 )); //bool(true)
var_dump ( is_int ( «23» )); //bool(false)
var_dump ( is_int ( 23.5 )); //bool(false)
var_dump ( is_int ( NULL )); //bool(false)
var_dump ( is_int ( «» )); //bool(false)

var_dump ( ctype_digit ( 23 )); //bool(true)
var_dump ( ctype_digit ( «23» )); //bool(false)
var_dump ( ctype_digit ( 23.5 )); //bool(false)
var_dump ( ctype_digit ( NULL )); //bool(false)
var_dump ( ctype_digit ( «» )); //bool(true)

var_dump ( isInteger ( 23 )); //bool(true)
var_dump ( isInteger ( «23» )); //bool(true)
var_dump ( isInteger ( 23.5 )); //bool(false)
var_dump ( isInteger ( NULL )); //bool(false)
var_dump ( isInteger ( «» )); //bool(false)
?>

The correct output for parts of his examples should be:

Keep in mind that is_int() operates in signed fashion, not unsigned, and is limited to the word size of the environment php is running in.

In a 32-bit environment:

( 2147483647 ); // true
is_int ( 2147483648 ); // false
is_int ( 9223372036854775807 ); // false
is_int ( 9223372036854775808 ); // false
?>

In a 64-bit environment:

( 2147483647 ); // true
is_int ( 2147483648 ); // true
is_int ( 9223372036854775807 ); // true
is_int ( 9223372036854775808 ); // false
?>

If you find yourself deployed in a 32-bit environment where you are required to deal with numeric confirmation of integers (and integers only) potentially breaching the 32-bit span, you can combine is_int() with is_float() to guarantee a cover of the full, signed 64-bit span:

= 2147483647 ; // will always be true for is_int(), but never for is_float()
$big = 9223372036854775807 ; // will only be true for is_int() in a 64-bit environment

I’ve found a faster way of determining an integer.
On my env, this method takes about half the time of using is_int().

Cast the value then check if it is identical to the original.

With this function you can check if every of multiple variables are int. This is a little more comfortable than writing ‘is_int’ for every variable you’ve got.

Simon Neaves’s answer is incomplete: negative integers will return false.

Источник

проверьте, простое ли число

Я пытаюсь создать функцию, которая проверяет, является ли число простым или нет. НО я хочу, чтобы эта функция отображалась для пользователя ‘prime’ или ‘NOT prime’ — и здесь начинается моя проблема.
Позвольте мне показать вам мой код:

Как я могу заставить его повторять только правильный ответ?

Решение

добавьте 10 байт для лучшей производительности:

добавьте еще 7 байтов для еще лучшей производительности:

Я не считал итераций, а только проверял потребление времени; и это только в TiO вместо контролируемой среды. Разница между двумя последними версиями была меньше, чем отклонение между несколькими прогонами.
Значимые результаты теста могут быть добавлены позже.

Другие решения

Вы можете проверить номер простое или нет & без использования цикла с этой функцией:

Это может быть длительной процедурой, если число действительно простое число. Есть и более короткая процедура.
Нам не нужно запускать цикл for до самого числа. Вместо этого мы можем запустить его до Наибольшее целое число меньше или равно квадратному корню из числа.

Теперь, в приведенном выше примере, если мы проверим, является ли 97 простым или нет (на самом деле, так оно и есть), то цикл не должен выполняться от 2 до 97, а только от 2 до 9. (Квадратный корень из 97 равен 9.8488578018, и наибольшее целое число, меньшее или равное этому, равно 9. Аналогично, мы можем проверить число 121 (это не простое число, так как оно делится на 11). В аналогичном случае предел будет увеличен с 2 до 11. И скоро.
На самом деле, нам нужно проверить делимость числа на меньшие простые числа в окрестности, но это было бы более сложно.
Надеюсь это поможет.

Вы можете найти простые числа и не простые числа от 1 до вашего лимита и его количество.

Разрыв только разрывает цикл for,
использование return; вместо. это выйдет из функции

Источник